면빈면빈면빈면빈

[적용한 알고리즘]

재귀

[아이디어]

다른 부분수열의 합과 동일

[생각의 흐름 / 절차] 

만들 수 있는 수들을 index 표시, 

반복문 돌면서 첫번째를 가져오면 될 것 같았다.

[교훈]

재귀를 더 연습하자.

직관적으로 와닿을 때까지.

<코드>

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n;
int arr[21];
bool check[20 * 100000 + 1];

void go(int index, int sum){
    if (index == n){
        check[sum] = true;
        return;
    }
    go(index + 1, sum + arr[index]);
    go(index + 1, sum);
}

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }

    go(0, 0);

    bool flag = false;
    for (int i = 0; i < 20 * 100000 + 1; i++){
        if (check[i]){
            flag = true;
        }
        else {
            if (flag){
                printf("%d\n", i);
                break;
            }
        }
    }

    return 0;
}

[적용한 알고리즘]

재귀

[아이디어]

X

[생각의 흐름 / 절차] 

경우의 수가 2^n 개이고 n<20 이니까 일일이 다 해봐도 괜찮겠다.

[교훈]

재귀를 더 연습해보자

<코드>

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int arr[20];
int ans;
int n, goal;

void go(int index, int sum){
    if (index == n){
        if (sum == goal){
            ans++;
        }
        return;
    }
    go(index + 1, sum + arr[index]); //부분 수열에 포함시키는 경우
    go(index + 1, sum); // 부분 수열에 포함시키지 않는 경우
}

int main(){
    scanf("%d %d", &n, &goal);

    for (int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }

    go(0, 0);
    if (goal == 0){
        ans--;
    }

    printf("%d\n", ans);

    return 0;
}

적용한 알고리즘 : 재귀

아이디어 : X

생각의 흐름 / 절차 : X

교훈 / 생각했던 점들 / 복기 :

뽑을 때 뽑지 않을 때를 각각 구분해서 재귀를 돌리자.

재귀는 사전 순을 나타낼 때 괜찮은 방법이다.

재귀가 약하니까 몇 문제 더 해봅시다.

<코드>

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

vector<int> lotto;

void solve(vector<int> &a, int index, int cnt){
    if (cnt == 6){
        for (int num : lotto){
            printf("%d ", num);
        }
        printf("\n");
        return;
    }

    int n = a.size();
    if (n == index) return;

    //index 번째 고름
    lotto.push_back(a[index]);
    solve(a, index + 1, cnt + 1);

    //index 번째 안고름
    lotto.pop_back();
    solve(a, index + 1, cnt);
}
int main(){
    while (true){
        int n;
        scanf("%d", &n);
        if (n == 0){
            return 0;
        }

        vector<int> a(n);
        for (int i = 0; i < n; i++){
            scanf("%d", &a[i]);
        }

        solve(a, 0, 0);
        printf("\n");
    }
}