https://www.acmicpc.net/problem/1208
문제는 여기에 있다.
🤔 왜 푸는 방법을 떠올리지 못했을까?
같은 문제인 BOJ 1182번 문제와 비교해서 다른점은 딱 하나인데 바로 N의 개수이다. 2의 40승이니 이것은 브루트 포스로 풀지 못하겠다는 생각을 떠올렸다. 하지만 dp로 구하는 방법도 딱히 떠오르지 않아서 무작정 분류가 이분 탐색이니 시작 인덱스부터 마지막 인덱스까지 2중 포문으로 하나씩 더해가면서 구해보려고 시도했다.
하지만
3 0
0 0 0
answer : 7
2 0
0 0
answer : 4
6 3
-1 -1 -1 1 1 1
answer : 1이런 케이스와 같이 중복 되는 것에 대한 처리가 전혀 안되고 예외 케이스도 너무 많았다.
그래서 dp를 배낭문제와 비슷하게 짜보려고 했지만 최댓값이나 최솟값을 구하는 것이 아니였기에 식을 짜기에 너무 헷갈렸다. 또한 나중에 dp로 풀어본 풀이가 있나 찾아보려고 했지만 메모리초과가 난다고 했다. (혹시 dp로 푸신 분이 있다면 댓글 부탁드립니다..!)
결국 풀이를 보았다. 두개로 나누어서 각 각 나눈 리스트 들의 조합의 합 배열을 만든 뒤에
그 두 개의 배열을 투포인터 형식으로 더해 가면서 찾으면 되는 것이었다. 두개로 나누면 각각 2^20개의 조합이 나오기 때문에 시간안에 풀이가 가능했다.
먼저 하나의 2^20 배열에 합이 목표한 값이 나오는 것들을 각각 세어주고,
배열 두개들 서로 투포인터로 비교하면서 그 두개의 합이 목표한 값이 나오면 더하는 방법으로 코드를 짰다.
가장 큰 원인은 문제에 대한 정확한 이해도가 떨어진 것이다. 다양한 케이스를 고려하지 못하는 것이 잘못된 풀이였음을 깨닫게 하는데에 시간이 오래걸리게 만들었다.
사실 알았어도 떠올리기 힘들었을 거 같기도 하고...
다음에 꼭 다시 풀어봐야 되는 문제중 하나인 것 같다..
항상 cs는 사람을 겸손하게 만드는 것 같다. 😭
다른 분들의 코드를 참고해 python으로 코드를 작성하였다.
https://github.com/Deserve82/KK_Algorithm_Study/blob/master/Kangho/BOJ_1208.py
