61. 특정 수 만들기[DFS]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

4 12

2 4 6 8

 

출력예제 1

4

 

풀이 

- 2, 4, 6, 8로 +, -, 사용X 의 경우로 나누어서 12를 만든다.

- 세 경우에 따라 DFS(L+1, sum+a[L]) / DFS(L+1, sum-a[L]), DFS(L+1, sum)이 된다.

- count값을 0으로 두고 count값이 변하지 않으면 해당 수를 만들 수 없기 때문에 -1을 출력한다.

- 경우의 수를 추적해보고 싶으면 path배열을 두고 DFS함수 시작 전에 경우에 따라 path[L]에 a[L], -a[L], 0을 넣어 준다.

- sum이 원하는 값과 맞아떨어질 때 for문을 통해서 1~L-1(이때 L은 내가 원하는 곳 다음곳까지 가있기 때문)까지 path의 값을 출력한다.

#include <stdio.h>
#include <algorithm>
using namespace std;
int n, m, a[11], answer=0, path[11];

//61. 특정 수 만들기
void DFS(int L, int sum){
    if(L==n+1){
        //완성된 경우
        if(sum==m){
            answer++;
            for(int i=1;i<L;i++){
                printf("%d ", path[i]);
            }
            puts(""); //줄바꿈
        }
    }else{
        path[L]=a[L];
        DFS(L+1, sum+a[L]);
        path[L]=-a[L];
        DFS(L+1, sum-a[L]);
        path[L]=0;
        DFS(L+1, sum);
    }
}

int main(){
    int i;
    scanf("%d %d", &n, &m);
    for(i=1;i<=n;i++){
        scanf("%d", &a[i]);
    }
    DFS(1, 0);
    if(answer==0) printf("-1\n");
    else printf("%d\n", answer);
    return 0;
}