BF(일반) - 기초(1)

BF에서 재귀를 쓰는 이유는 그냥 for문 중첩으로 풀기에는 for문이 너무 많아져서 그렇다

2309번: 일곱 난쟁이 (acmicpc.net)

2309번: 일곱 난쟁이

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;

const int ans = 100;
int main(void)
{
    freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    vector<int> d(9);
    int sum = 0;
    for(int i = 0 ; i < 9 ; ++i)
    {    
        cin>>d[i];
        sum += d[i];
    }
    sort(d.begin(), d.end());

    int i,j,k;
    for(i = 0 ; i < 9 ; ++i)
    {
        for(j = i+1 ; j < 9 ; ++j)
        {
            if(sum - d[i] - d[j] == ans)
            {
                for(int k = 0 ; k < 9 ; ++k)
                {
                    if(k == i || k ==j) continue;
                    cout<<d[k]<<'\n';
                }
                return 0;
            }
        }
    }
    
    return 0;
}

 

 

---

 

N과 M 계열의 문제는 재귀적으로 문제를 푸는데 큰 도움이 된다.

 

15649번: N과 M (1) (acmicpc.net)

15649번: N과 M (1)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
// algorithm의 swap과 max를 쓰자

int a[9];
bool check[9];
void go(int i, int m, int n)
{
    if(i == n)
    {
        for(int j = 0 ; j < n ; ++j)
        {
            cout<<a[j];
            if(j != n-1) cout<<' ';
        }
        cout<<'\n';
        return;
    }
    for(int j = 1 ; j <= m ; ++j)
    {
        if(check[j]) continue;
        a[i] = j;
        check[j] = true;
        go(i+1, m,n);
        check[j] = false;
    }
}
int main(void)
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n,m;
    cin >> m >> n;

    go(0, m, n);
    return 0;
}

m과 n문제를 풀어보면 재귀문이 어떻게 구성되어야 하는지 알게된다.

매개변수로는 for 반복문과 동일하게 구성해준다(인덱스, 제한값, 저장데이터)

매개변수를 자주 쓰는게 귀찮다면 저장데이터는 전역변수로 넘겨주어도 된다.

 

코드 구성도 깔끔하다.

 

for 반복문에서도 언제 종료될지 넣는 것과 같이 제일먼저 탈출 조건과 탈출시 작동할 코드를 넣어주고

이 아래에는 for 문을 하나 더 넣어 주어서 모든 경우를 실행해준다.