군대에서_코딩하기_알고리즘_25

신태원·2021년 12월 1일
0

군대에서_코딩하기

목록 보기
26/30
post-thumbnail

깊은 깨달음...
아니 한참 공부 잘하고 있었는데, 갑자기 대대 사지방에 인터넷이 안되는 바람에 며칠동안 연등을 못했다.. + 어제는 야간근무 초번이여서 못함..
이게 물들어올때 노저어야한다고..한창 학구열에 불타서 잘하고 있었는데.. 또 며칠동안 안봤다고 기억이 가물가물했다..
근데 다행히도 저번에 DFS정리를 매우 잘해놨기 때문에, 정말 처음으로 내가 올려놓은 글을 다시 읽으며 복기를 했다 매우 뿌듯 ㅎㅎ

아무튼 오늘의 문제는

특정 수 만들기(DFS: MS 인터뷰)

이런 문제이다..
그동안..아니 사실 그동안이라고 할것도 없지만 지금까지 해왔던 DFS들은 갈래가 2개였던 이진트리였지만, 이번문제는 인덱스 하나당 경우의 수가 3개가 필요하다.

위 그림처럼, 2가 존재하지 않거나, 양수로 적용되거나, 음수로 적용될 때 총 3가지의 경우의 수로 뻗어나가기 때문에, 갈래가 총 3개인 트리를 사용해야한다.

우선 코드는 다음과 같다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int num[11]={0,};
int N;
int make;
int cnt=0;
bool flag = false;

void DFS(int level, int sum){
    
    if(level==N+1){
        if(sum==make){
            flag = true;
            cnt++;
        }
        return;
    }
    else{
        DFS(level+1, sum);
        DFS(level+1, sum+num[level]);
        DFS(level+1, sum-num[level]);
        
    }
    
}



int main(){
    
    cin>>N;
    cin>>make;
    for(int i=1; i<=N; i++){
        cin>>num[i];
    }
    
    DFS(1, 0);
    
    if(flag){
        cout<<cnt;
    }
    else{
        cout<<-1;
    }
    
}

저번에 업로드했던 문제에는 부분집합들을 다 돌면서, total에서 지금까지 더했던 sum값을 뺐을 때 자기자신이 나오면 탐색을 '그만'해도 됐다.
그래서 level이 N+1에 닿기 전에도 어떠한 조건을 만족하면 바로 탐색을 중지하고 다시 위로 올라가게끔 했는데, 이번에는 일단 밑까지 다 찍고와서 cnt++를 해주는 형식이기 때문에 함부로 return을 시켜버리면 안된다.

말이 좀 어려워도 아무튼 나는 뭔가 오늘 조금의 깨달음이 있었고 이제 조금 DFS가 뭔지 알것같다.

profile
일단 배우는거만 정리해보자 차근차근,,

0개의 댓글