61강

💎 문제

💎 소스

#include <stdio.h>
#include <algorithm>
#include <stack>
#include <vector>
#include <iostream>
#include <math.h>
using namespace std;

int n,m;
int num[11];
int sum=0;
int cnt=0;

void DFS(int k, int value){
	if(k > n){
		if(value == m) cnt++;
		return;
	}
	DFS(k+1,value+num[k]);
	DFS(k+1,value);
	DFS(k+1,value-num[k]);
}

int main(){
	//freopen("input.txt", "rt", stdin);
	scanf("%d %d",&n,&m);
	for(int i=1 ; i<n+1 ;i++){
		scanf("%d",&num[i]);
	}
	DFS(1,0);
	printf("%d",cnt);
}

	
	

💎 내생각

• 이 문제에서 가장 중요하게 생각해야 할 점은 레벨순회라는 점이었다.

• 레벨순회라는 것은 현재 트리구조에서 하나의 레벨에는 각각 가지고 있는 값들이 존재한다.

• 이 존재하는 값들 중 하나씩을 기억해서 답을 도출해내는데 사용하는 것이 레벨순회이다.

• 따라서 이와 같은 경우 처음 레벨부터 끝 레벨까지 순회를 했을때에 대해서만 답을 도출 할 수 있기 때문에 트리의 구조상 null값을 가지고 있는 트리의 말단 노드들을 호출 했을 때에 앞에서 기억한 값들을 토대로 정답을 도출 할 수 있게 된다.

• 또한 기억해야 할 점이라고 생각하는 것은 순회의 방식이다. DFS는 현재 재귀호출 되고 있다. 재귀호출이 일어날 때, 이 호출된 함수는 자신의 모든 자식들을 호출한다. 그리고 그 밑에 모든 자식들이 종료 됐을 때, 자신의 부모 노드로 가게된다.

• 위의 것을 말한 이유는 말단노드를 살펴보기 위함이다. 말단 노드는 자식들이 모두 null값을 가지고 있으며 if문을 통해서 걸러지게 된다. 이 경우 재귀호출을 하지 않기 때문에 바로 자신의 부모노드로 올라가게된다. 즉 이번 문제 같은 경우 하나의 부모에 달라 붙어있는 말단 노드들은 총 부모를 세번 호출한다. 이 호출에도 순서가 있는데, 부모노드 -> 첫번째 노드 종료 -> 부모노드 -> 두번째노드 종료 -> 부모노드 -> 세번째노드 종료 -> 부모노드 종료 순으로 중간 중간에 부모노드를 거치게 된다.