[Inflearn] 특정 수 만들기(DFS) (MS interview source)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

     - 집합의 원소와 '+' '-' 연산을 사용하여 특정 수인 M 을 만드는 경우의 수

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

이전 문제와 유사하다.

4 12

2 4 6 8

단, 여기서는 한 원소에 대하여 더할 경우,뺄 경우,사용하지 않을 경우

이렇게 세 가지의 경우가 있기 때문에

함수 호출 구조에서 각 함수가 세 개씩의 자식을 갖게 될 것이다. 

아래와 같이 그림을 그려보면서 대략적인 코드를 짜보았다.

if(sum == M)  // 이 부분은 sum 이 M 과 일치하는데 굳이 더 깊이 내려갈 필요는 없을 것 같아 따로 조건문을 두었다.

{

cnt++;

return;

}

else if(sum > M) return;   // 처음에 이 부분을 넣었었는데, 정답이 제대로 나오지 않았었다.

왜냐..! 빼는 연산도 있기 떄문에 마지막 레벨까지는 무조건 가봐야 알기 떄문이다.

if(lv == n + 1) return;

else

{    // 세 개의 줄기

f(lv + 1, sum + a[lv]);    // 더할 경우

f(lv + 1, sum - a[lv]);    // 뺄 경우

f(lv + 1, sum);            // 사용하지 않을 경우

}

    

sum 과 M 이 일치할 경우 굳이 더 깊이 내겨갈 필요가 없다고 생각해서 return 하도록 구현을 하였는데,

틀리는 testcase 가 생겨버린다..

대체 왜지!? 디버깅을 해보자..

확인결과 입력으로

7 11

3 4 7 5 8 9 1

가 주어졌을 때,

아래와 같은 일이 일어났다...!

위 코드를 삽입했을 경우

3 -4 7 5

정상적인 코드를 동작할 경우

3 -4 7 5 8 -9 1

3 -4 7 5 -8 9 -1

여기서 보면 위 코드를 동작시켰을 때,

3 -4 7 5 까지 탐색을 하고 끝내버리는데, 

이 문제에서 원하는 포인트는 리프노드까지 sum을 한 결과가

M 인 경우를 찾길 원했던 것 같다. 

그래서 결국에는 sum == M 의 조건을 

리프노드까지 탐색을 완료했을 때 넣어주어야 할 것 같다.

if(sum == M)  

{

cnt++;

return;

}

if(lv == n + 1) 

{

if(sum == M)  

cnt++;

return;

}

else

{    // 세 개의 줄기

f(lv + 1, sum + a[lv]);    // 더할 경우

f(lv + 1, sum - a[lv]);    // 뺄 경우

f(lv + 1, sum);            // 사용하지 않을 경우

}

어떻게보면 연산 결과가 M 인 집합을 만드는게 목적이니까

3 -4 7 5 8 -9 1

3 -4 7 5 -8 9 -1

는 서로 다른 집합이니까? 그런 것 같다.

#. Code

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m, a[11], cnt = 0;
 
void DFS(int lv, int sum)
{
    if (lv == n + 1)
    {
        if (sum == m)
            cnt++;
 
        return;
    }
    else
    {
        DFS(lv + 1, sum + a[lv]);
        DFS(lv + 1, sum - a[lv]);
        DFS(lv + 1, sum);
    }
}
 
int main(void)
{
    //freopen("input.txt", "rt", stdin);
 
    int i;
 
    scanf("%d %d", &n, &m);
 
    for (i = 1; i < n + 1; i++)
        scanf("%d", &a[i]);
 
    DFS(1, 0);
 
    if(cnt)
        printf("%d\n", cnt);
    else
        printf("-1\n");
 
    return 0;
}

#. Other code

#include<stdio.h>
#include<algorithm>
#include<queue>
 
using namespace std;
 
int a[11], n, m, cnt=0;
 
void DFS(int L, int sum){
    if(L==n+1){
        if(sum==m){
            cnt++;
        }
    }
    else{
        DFS(L+1, sum+a[L]);
        DFS(L+1, sum);
        DFS(L+1, sum-a[L]);
    }
}
 
int main(){
    int i;
    scanf("%d %d", &n, &m);
    for(i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }
    DFS(1, 0);
    if(cnt==0) printf("-1\n");
    else printf("%d\n", cnt);
    return 0;
}
 

> 경로 확인 체크

#include<stdio.h>
#include<algorithm>
#include<queue>
 
using namespace std;
 
int a[11], n, m, cnt=0, path[10];
 
void DFS(int L, int sum){
    if(L==n+1){
        if(sum==m){
            cnt++;
            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]=0;
        DFS(L+1, sum);
        path[L]=-a[L];
        DFS(L+1, sum-a[L]);
    }
}
 
int main(){
    int i;
    scanf("%d %d", &n, &m);
    for(i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }
    DFS(1, 0);
    if(cnt==0) printf("-1\n");
    else printf("%d\n", cnt);
    return 0;
}

#. Result

  - Input --------------------------------------------------------

4 12

2 4 6 8

------------------------------------------------------------------

  - Output --------------------------------------------------------

4

------------------------------------------------------------------