결론적으로 말하자면 BFS, DFS 개념은 이해했지만 실제적으로 아직 어떻게 응용하는지에 대해서 잘 몰라서 못 풀었다.
다른 분의 코드를 봤는데 정답이 왜 정답인지 이해하기 위해서 그림판으로 그리면서 보게 되었고, 이해한 것을 공유하기 위해 작성.
문제는 짧아서 간단하다. 문제 링크
문제 이해
예제 입력 1에서 수열을 보자면 { -7, -3, -2, 5, 8} 이 수열이 될 것이다.
부분수열은 {}, {-7}, {-3}, {-2, 5} 등 말 그대로 수열 중의 일부분을 자른 것이라고 생각하면 된다.
그러면 다시 예제 입력 1 기준으로 문제를 살펴보면 다음과 같이 정의할 수 있다.
5개의 정수를 입력받을것이고 5개 정수 중 어떤 걸 조합해서 0을 만들 수 있는 부분개열의 개수를 구하라
예제 출력1이 1인 이유는 0을 만드는 부분수열은 {-3, -2, 5} 일 때만 정답인 0을 만족시키기 때문이다.
정답은 되게 많은데 일단
이분 것을 참고했다.
정답 코드
가기 귀찮은 사람을 위해 투척.
정답 이해
코드만 보면 그래서 뭔데라고 생각할 수 있어서 이해하기 힘들 수도 있다 (나도 그랬음..)
그래서!!! 무식하지만 예제입력1에 대해서 그림판으로 그렸다.
문제에서 정답을 구하기 위해서는 항목들을 각각 더해봐야 한다.
{ -7, -3, -2, 5, 8}에서 각 항목들이 0이 되는 조합을 만들기 위해 각 항목을 더해봐야 한다.
그럼 처음에는
- -7을 사용하지 않는 경우
- -7을 사용하는 경우
두가지가 존재한다. 우리는 -7을 넣으면 뭘 해도 0이 나올 수 없는 것을 알기 때문에 -7을 사용하는 경우는 제외하고 생각해보자.
해당 숫자를 사용하지 않는 경우 0 더하는 것과 마찬가지다.
7을 사용하지 않고, 다음 항목인 -3부터 본다면 아래 그림판처럼 트리 구조로 나온다. (근데 2의 n제곱개로 가기 때문에 좀 지저분해서 마지막은 들쭉날쭉한 것 양해 부탁드립니다...)
탐색을 중단할 경우는 지금까지 더한 값이 S(현재 입력 : 0)이 될 때이다. 왼쪽의 검은 선을 따라가면 모두 더한 값이 0이 되어 리턴해주고, 더한 값이 정답이 되는 수열을 1개 증가시키고 탐색을 종료해 준다.
44번째에서
int result = (S == 0) ? answer - 1 : answer;를 해주는 이유는 S ( 모두 더한 값)이 0이어야 할 때 그림판의 맨 오른쪽을 보면 0 -> 0 -> 0 -> 0 -> 0으로 되는 경우를 볼 수 있다.
그렇기 때문에 S가 0일 때는 빼주지 않으면 0 -> 0 -> 0 -> 0 -> 0 도 answer에 포함되기 때문에 1개씩 빼줘야 정답이 된다.
결론
알고리즘... 어려워...
이론은 알겠는데 실제로 응용에 익숙해질 때까지 반복해서 풀어봐야 겠다.