인프런 8-1. 합이 같은 부분집합 (자바)

[문제]

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 
두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 
”NO"를 출력하는 프로그램을 작성하세요.
둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 
집합이 되어 합니다.
예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 
16으로 같은 경우가 존재하는 것을 알 수 있다.


[입력설명]

첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.


[출력설명]

첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.


[입력예제 1]

6
1 3 5 6 7 10 


[출력예제 1]

YES

---

[문제풀이과정]

쟤는 그럼 가능한 한 모든 경우의 수를 다 따져야되네? 두 집합이 서로소이고
합집합이 전체집합이니까 칸을 두개로 나눠놓고 N개의 원소한테 어디로 갈지 물어보면 2를 N번 곱한
2^N 만큼의 경우의 수가 나오게 된다.
다행히 N은 10까지만이므로 최대한 경우의 수를 많이 고려하더라도 1024번만 따져보면 된다.
음 일단 예시에는 수가 알아서 오름차순으로 나와있지만 실제로는 그렇지 않을수도 있으므로
일단 배열 속 숫자를 오름차순으로 정렬하자.
그리고 큰 숫자들끼리 작은 숫자들끼리 모여있을 리가 없으므로
큰 숫자와 작은 숫자를 짝지으며 경우를 따져보기 시작한다.

음.. 아니 아니지?? 큰 숫자 두개랑 나머지 숫자 전부다랑 똑같을 수 있으므로 
합칠때 큰 숫자끼리 합쳐도 된다.
그럼 그냥 내림차순으로 정렬할까??
아니 어쩌면 정렬이 중요하지 않을지도...
어쨌든 저기서 만약에 2개 VS 4개 조합으로 뽑는다고 할때
'조합'을 나타내는 방법이라서 사실상 오름차순 정렬이 무의미하다.

아.. 너무 어려운데? 일단 [1, 2, 3, 4] 라는 배열이 있다고 하고
얘네를 한개 뽑기 두개 뽑기 세개 뽑기 네개 뽑기 이렇게 조합으로
뽑는다고 하자.

[참고한 블로그]

https://gyuwon95.tistory.com/136

일단 i = 0일때, combination(arr, visited, 0, 0, 1)이 가장먼저 실행됨
depth인 0과 r인 1이 다르므로 else를 타고,
그 안에서 visited[0] == false 이므로 else를 타면
visited[0]을 true로 바꾸고
combination(arr, visited, 1, 1, 1)을 실행한다.

그럼 depth인 1과 r인 1이 같으므로 if를 타고,
그 안에서 반복문을 돈다! 먼저 i가 0인데
visited[0] == true이므로 arr[0]인 1을 출력한다.
i가 1이면 visited[1] == false이므로 출력하지 않는다. i=2,3도 마찬가지로 출력 X

그리고 다시 else문으로 돌아와서 visited[0]을 false로 돌려놓고 끝.
이제 else안에서 i가 1이면 visited[1] == false이므로
visited[1]을 true로 바꾸고
다시 combination(arr, visited, 2, 1, 1)을 실행한다.

그럼 depth인 1과 r인 1이 같으므로 if를 타고,
그 안에서 반복문을 돈다! 먼저 i가 0인데
visited[0] == false이므로 arr[0]은 출력하지 않고
i = 1이면 visited[1] == true이므로 arr[1]을 출력한다. i=2,3은 0과 마찬가지로 출력 X

그리고 다시 else문으로 돌아와서 visited[1]을 false로 돌려놓고 끝.
이제 else 안에서 i가 2이면 visited[2] == false이므로 똑같이 반복.
visited[3]까지 해서 다 완료.

그렇게 
1
2
3
4
이렇게 찍힘!!!

그럼 main 함수 속 for문에서 이제 겨우 한번 돈 거임!!
그럼 이제 i가 1이 되고,
combination(arr, visited, 0, 0, 2)이 실행됨.

그럼 depth인 0과 r인 2가 다르므로 else를 타고,
그 안에서 visited[0] == false 이므로 else를 타면
visited[0]을 true로 바꾸고
combination(arr, visited, 1, 1, 1)을 실행한다.


아 근데 너무 어려워서 도저히 해석할 수가 없다!!
유튜브에서 알고리즘 조합을 검색하고 설명을 들어보니
a, b, c 이렇게 세가지를 뽑는 조합을 검색하려면
a - b
a - c
b - c
이렇게다!! 즉 시작점이 a일때는 b와 c 모두로 가야되는데
시작점이 b일때는 a로는 갈 필요 없다! 내 다음인 c로만 가면된다.
그리고 c는 맨 마지막이기 때문에 어디로도 갈 필요가 없는것!!
즉 조합에서는 시작점이 어딘지가 중요하다!!
한번 탐색할 때마다 시작점에 +1 해주면 된다!

 

[Java] 순열(Permutation), 조합(Combination)

그런데 아무리 생각해도 조합으로 부분집합 만들수 있는 모든 경우의 수를 나타낸다 해도 그 다음에 어떻게 할지 예측이 안 된다... 왜냐면 나는 부분집합의 '합'을 비교해야되니까.. 그럼 배열 속에 있는 숫자를 또 다 더해? 반복문 써서? 배열속 숫자가 엄청 많을텐데? 뭔가 아닐것같다... 내가 아직 못 풀어낸 프로그래머스의 던전 문제와 비슷하게 DFS.. 머 재귀함수.. 그런걸 써서 풀어야하는 것 같다.

그래서 유튜브로  DFS BFS 풀이에 대해 찾아봤다. 그런데 다들 뭔 노드를 연결해서 뭐 자식노드 부모노드 어쩌구.. 개념적인 얘기를 그것도 아주 알아듣기 어렵게 설명하고 코드로는 잘 안 알려줬다. 그래서 이 문제를 정말정말 스스로 해결해보고 싶었지만 어쩔수 없이 해설강의를 먼저 듣게 되었다...!! 끄흐그흐으으러어러어어어엉어엉ㅇ어어어ㅠㅜㅜㅠㅠㅠ

암튼 던전 문제랑 비슷하게 뭔가 depth를 따져서 하는것 같았고, 마치 경우의 수에서 가지치기 하듯이 맨 처음 경우에서 그 다음 경우를 가느냐 마느냐로 전부 선택하고 그리고 그 각각의 경우들에서도 그 다음 경우로 가느냐 마느냐를 계산하는 방식으로 하고 있었다. 인강을 먼저 듣고 내 나름대로 노트에 필기해가며 생각을 정리하고 코드로 옮겨보려고 했다.

이건 뭐냐면 크리스마스 트리에서 꼭대기부터 시작해서 밑으로 내려온다고 생각하면 된다. D(0, 1)에서 왼쪽 숫자는 depth, 즉 이 배열에서는 index를 의미한다. 숫자가 6개뿐이므로 index는 당연히 0에서부터 시작해서 5까지만 내려간다. 그리고 오른쪽 숫자는 선택한 원소들의 합 SUM이다. 아무튼 어차피 모든 원소가 두 부분집합 중 한곳에는 무조건 들어가야 하므로 0번째 원소부터 시작해서 그 다음 1번째 원소를 뽑을지 안 뽑을지, 그리고 각각의 경우에서는 그 다음 2번째 원소를 뽑을지 안 뽑을지 이런식으로 가능한 한 모든 조합으로 SUM을 계산해 나가는 거다! 그리고 무조건 6번 다 해야된다. 어차피 6개의 원소가 뽑히고, 뽑히고, 뽑히고, 안 뽑히고, 뽑히고, 안 뽑히고 이런 식으로 계산 될 거니까!@!! 암튼 이런 식으로 문제 풀이 방법을 먼저 구체화시키고, 이제 코드로 옮겨 보려고 했는데 재귀함수 한번도 배워본 적도 없고 짜본적도 없는 내게는 쏘 디피컬트한 것..... 그래서 이것또한 어쩔 수 없이 먼저 해설강의를 보고서는 했다ㅜㅜ 그래도 보면서 바로 안 베끼고 먼저 보고 이해한 대로 기억만 하고 그대로 코드를 짜려고 해본 결과 이러한 결과가 나왔다.

[해설강의 보고 처음으로 짠 코드 -> 테스트 케이스 실패함]

import java.util.Scanner;

public class Main {
	static boolean flag = false;
	// DFS가 끝났을 때에만 깃발을 들어 끝을 알리겠음
	static int total = 0;
	// 집합 속 원소 총합
	static String answer = "NO";
	static int N = 0;
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
	    N = sc.nextInt();
	    int[] arr = new int[N];
	    int sum = 0;
	    
	    for(int i = 0 ; i < N ; i++) {
	    	arr[i] = sc.nextInt();
	    	// 원소 N개 짜리 배열에 숫자 N개 넣어주기
	    	total += arr[i];
	    	// 원소 전부 더한 총합 구해야됨
	    }
	    
    	DFS(0, arr[0], arr);
    	// DFS 함수 실행! 0번째 깊이(인덱스)와 합계 기억하기
    	
    	System.out.println(answer);
	  }

	private static void DFS(int depth, int sum, int[] arr) {
		if(flag) {
			return;
			// 이미 만족하는 조건 찾았으면 다른 DFS들 구할 필요 없음!!
		} if(sum > (total / 2)) {
			return;
			// 큰 숫자들을 더해버려서 도중에 목표값을 넘는다? 그럼 할 필요 없음
		} 
		
		if(depth == N-1) {
			// 부분집합이 완성됐을때임!
			// 6개의 원소를 다 넣었다는 소리가 아님.
			// 우리는 각각의 원소를 넣은 경우 안 넣은 경우 모두 계산했으니까.
			if(sum == (total / 2)) {
				flag = true;
				answer = "YES";
				return;
				// 목표값에 도달하면 끝났다고 깃발 세우고 더이상 할 필요 없음
			} // 끝까지 와버렸는데 목표값에 도달했으면 YES인 것
			// 그게 아니면 그냥 원래값인 NO로 냅두면 됨
		} else {
			DFS(depth+1, sum + arr[depth+1], arr);
			// 다음 인덱스 값을 더한 DFS 하나랑
			DFS(depth+1, sum, arr);
			// 다음 인덱스 값을 안 더한 DFS 하나 이렇게 총 두개씩 만들어 나가면됨!
		}
	}
}

이렇게 했는데 다섯개의 테스트 케이스중 어떤 한개가 자꾸 NO인데 나는 YES라고 잘못 나오는것!! 강사님의 풀이를 보니 특이하게 main 함수에서 Main T = new Main() 이런식으로 클래스를 생성하고  T.DFS(어쩌구) 요렇게 클래스 안의 함수를 쓰겠다 이런식으로 썼고 그리고 나랑 다른 점은 나는 맨 처음 노드부터 sum 에 arr[0]의 값을 담았지만 해설지에는 처음엔 0으로 시작하고 depth 1부터 arr[0]의 값을 담는 식으로 한칸씩 미뤄서 진행했달까..? 그래서 아무리 생각해도 왜 틀렸는지 모르겠지만서도 그래도 강사님 풀이랑 토씨하나 틀리지 않게 바꿔봤다. 그런데도 계속 오류가 났다.

그래서 사람들이 커뮤니티에 질문 올려놓고 강사님이 답변 달아준 것을 보니 세상에 마상에나!! 어찌 보면 사소하지만 어찌보면 너무너무 중요한 부분에서 내가 치명적인 실수를 저질렀다!! 바로 sum == (total / 2) 이 부분!!! /는 몫을 의미하기 때문에 홀수를 2로 나누면 실제 값은 소수점이 나오더라도 몫이라서 깔끔한 정수가 나와버린다. 그래서 부분집합에서의 합이 모든 원소의 합의 절반과 같지 않은데 우연히 몫이 맞아떨어져서 자꾸만 틀린 결과를 내고 있었던것!! 세상에나!! 아니 어쩐지 강사님은 자꾸 sum == (total - sum) 이렇게 하길래 도대체 왜 저렇게 하나 했는데 이런 이유였었다. 암튼 지금 이걸 틀렸으니 얼마나 다행이여??

---

[수정해서 통과한 나의 풀이]

import java.util.Scanner;

class Main {
	static boolean flag = false;
	// DFS가 끝났을 때에만 깃발을 들어 끝을 알리겠음
	static int total = 0;
	// 집합 속 원소 총합
	static String answer = "NO";
	static int N = 0;
	
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
	    N = sc.nextInt();
	    
	    int[] arr = new int[N];
	    
	    for(int i = 0 ; i < N ; i++) {
	    	arr[i] = sc.nextInt();
	    	// 원소 N개 짜리 배열에 숫자 N개 넣어주기
	    	total += arr[i];
	    	// 원소 전부 더한 총합 구해야됨
	    }
	    
    	DFS(0, arr[0], arr);
    	// DFS 함수 실행! 0번째 깊이(인덱스)와 합계 기억하기
    	
    	System.out.println(answer);
	  }

	public static void DFS(int depth, int sum, int[] arr) {
		if(flag) {
			return;
			// 이미 만족하는 조건 찾았으면 다른 DFS들 구할 필요 없음!!
		} if(sum > (total - sum)) {
			return;
			// 큰 숫자들을 더해버려서 도중에 목표값을 넘는다? 그럼 할 필요 없음
		} 
		
		if(depth == N-1) {
			// 부분집합이 완성됐을때임!
			// 6개의 원소를 다 넣었다는 소리가 아님.
			// 우리는 각각의 원소를 넣은 경우 안 넣은 경우 모두 계산했으니까.
			if(sum == (total - sum)) {
				flag = true;
				answer = "YES";
				// 목표값에 도달하면 끝났다고 깃발 세우고 더이상 할 필요 없음
			} // 끝까지 와버렸는데 목표값에 도달했으면 YES인 것
			// 그게 아니면 그냥 원래값인 NO로 냅두면 됨
		} else {
			DFS(depth+1, sum + arr[depth+1], arr);
			// 다음 인덱스 값을 더한 DFS 하나랑
			DFS(depth+1, sum, arr);
			// 다음 인덱스 값을 안 더한 DFS 하나 이렇게 총 두개씩 만들어 나가면됨!
		}
	}
}

이렇게 조건 하나만 바꿔줬더니 예쁘게 모든 테스트 케이스가 통과했당~~!!! 내가 자꾸 / 을 분수의 가운데 작대기 처럼 생각해서 머릿속으로 쩜몇까지 완벽하게 '실수(float)'로 인식해버리는것 같다. 그래서 저번에도 뭐 계산할때 되게 간단한걸 되게 어렵게 계산해서 수정한적 있었는데? 과외 첫날 풀었던 문제? 뭐 암튼암튼!! 앞으로는 이걸 꼭 주의하도록 하자~!

오늘 DFS 문제는 처음 풀어봤는데 재귀함수를 처음 다뤄봐서 너무 어려웠지만 그래도 산 하나 넘었으니 앞으로 비슷한 문제는 풀 수 있겠딩~!!