깊은 깨달음...
아니 한참 공부 잘하고 있었는데, 갑자기 대대 사지방에 인터넷이 안되는 바람에 며칠동안 연등을 못했다.. + 어제는 야간근무 초번이여서 못함..
이게 물들어올때 노저어야한다고..한창 학구열에 불타서 잘하고 있었는데.. 또 며칠동안 안봤다고 기억이 가물가물했다..
근데 다행히도 저번에 DFS정리를 매우 잘해놨기 때문에, 정말 처음으로 내가 올려놓은 글을 다시 읽으며 복기를 했다 매우 뿌듯 ㅎㅎ
아무튼 오늘의 문제는
이런 문제이다..
그동안..아니 사실 그동안이라고 할것도 없지만 지금까지 해왔던 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가 뭔지 알것같다.