dp로 풀어야 한다.
d[cur][pre] = 현재 수가 arr[cur]이고 이전의 수가 arr[pre]인 경우의 등차 수열인 부분 수열의 개수
d[cur][pre] = pre-ppree==cur-pre 인 경우, d[pre][ppre]+1 (원래 ....pppre-ppre-pre-cur 로 이루어진 수열의 개수와 ppre-pre-cur 수열의 1개를 더해준 것)
근데 이렇게 할 경우 O(N의 세제곱)정도의 시간복잡도가 나오기 때문에 좀 힘들어보인다... 일단 C++로는 99개의 테스트 케이스 대부분을 통과했지만 내 기억으로는 98번째 데이터에서 시간초과를 받았다. 그런데 그 코드를 그대로 자바 코드로 옮겨서 제출했더니 통과했다...
음.. 일단 이 문제 관련 discussion 게시판에 가서 O(N제곱)이 걸리는 풀이를 봤다.
힌트에는 binary tree라고 되어있었는데... 보니까 map을 쓰는 것이었다.
그럼 정확히는 O(N제곱*logN)인가... 여튼, 예전에 이런 식으로 푸는 문제를 본 적이 있는 것 같은데... 전혀 생각도 못했다.
d[cur][by] = arr[cur]를 마지막으로 하고 차이가 by인 등차수열의 개수
로 하는 것 같다. 이 방법은 사실 처음에 생각했던 방법인데, 차이값이 최대 int형 범위까지 나올 수 있어서 너무 크기 때문에, 그리고 음수가 나올 수도 있기 때문에 배열을 못 잡을 것이라고 생각했다... 아 그런데 map이 있었지... map을 이용한 dp... 예전에 풀었던 것 같은데... 그래도 지금이라도 봤으니 다행이다.
d[cur][by] = SUM(arr[cur]-arr[pre]==by인 pre에 대하여, d[pre][by]+1)
이 될 것이다.
그리고 by는 최대 N개가 나올 수 밖에 없으므로 모든 수에 대해 다 돌리지 말고 N개의 by에 대해서만 보면 된다.
이게 구현하는 과정에서 좀 고려해야할 것이 있다. 이 문제에서 요구하는 등차수열은 길이가 3이상이어야 한다. 그렇기 때문에 길이가 2인 등차수열을 잘 처리해줘야 하는데...
1, 1, 2, 3 이 주어지면 아마 1, 2, 3을 두 개 만들 수 있으므로 2가 나와야 하는데 나는 보통은 두 개 짜리의 개수는 항상 0으로 처리해서 이 경우 1이 나왔다.
그리고 최종 답은 cur, by에 대해 모든 경우를 다 더해봐야 하는데, 두 개인 경우가 0일 때는 괜찮았는데, 두 개인 경우도 개수를 부여하면 이제는 두 개인 경우가 뭔지 구분을 해야하는데... 어렵다..
그래서 고민 끝에 재귀로 한 번 짜보기로 했다. 재귀로 해도 여전히 어렵다...
결국 다시 discussion의 정답 코드를 분석해보다가 이해했다.
지금 문제가 두 개인 경우는 등차수열이 아니기 때문에 0으로 처리할 경우 1, 1, 2, 3 같은 예제에서 cur==2, by==1일 때 경우의 수가 0이되어 답이 1이 나오게 되는 것인데...
(문제를 다시 잘 읽어보면 1, 2, 3이라고 경우의 수가 1이 되는 것이 아니다. 인덱스상으로 1, 2, 3은 두 가지가 나온다. 문제에서는 인덱스를 기준으로 해서 등차수열의 개수를 구하라고 하고 있다.) 정답 코드들은 길이가 2인 경우를 0으로 치지 않고 개수가 있는 것으로 친다. 즉, 길이가 2인 경우도 센다(count한다).
그러면 또 위에서 고민했던 두 개인 경우가 뭔지 구분해서 최종 답에는 합산하지 않아야 한다. 하지만 그렇게 처리하지 않는다. 등차수열이 되는 경우를 보자. 길이가 3인 어떤 등차수열X의 개수는 (수열X에 포함되는 길이가 2인 등차수열 개수)들의 합이된다. 결국 길이가 3인 등차수열의 개수를 구하면서 최종 답 ans 변수에는 길이가 3인 등차수열의 개수를 구할 때 이용되는 길이가 2인 등차수열의 개수를 더해준다.
그리고 코드상으로는 길이가 3인 등차수열의 개수에 +1을 해준다.
그렇다면 길이가 3인 등차수열의 개수는 어디에 쓸까? 바로 길이가 4인 등차수열의 개수를 구할 때 쓸 것인데, 이제 여기서부터는.. 길이가 4인 등차수열의 개수는 (길이가 3인 등차수열 개수 + 1) 들의 합이다. +1이 의미하는 것은 길이가 하나 늘어나면서 끝에서부터 길이가 3개짜리인 등차수열이 하나 더 생긴다는 의미이다. 하지만 +1은 나중에 해주고, ㅇ위에서 처럼 (길이가 3인 등차수열 개수)들의 합을 최종 답ans에 더해주고, 길이가 4인 등차수열의 개수로 저장한다.
현재 길이가 2인 등차수열의 개수를 인정했기 때문에 길이가 2인 등차수열의 개수는 사실 길이가 3인 등차수열의 개수를 뜻하게 되고, 길이가 3인 등차수열의 개수는 (길이가 2인 등차수열의 개수+1한 값들의 합이기 때문에) 길이가 4인 등차수열의 개수를 가리키게 된다... 즉, 이렇게 계속 길이가 n인 등차수열의 개수를 구해 나가되, 실제로는 길이가 n+1인 등차수열의 개수를 의미하므로 최종답 ans에는 길이가 2인 등차수열의 개수부터 n-1인 등차수열의 개수만 저장하면 되는 것이다.
(참고로 이해를 위해 등차수열의 길이를 언급했지만 사실 등차수열의 길이를 이용해서 푸는 것은 아님.)
여기서 중요한 것은 같은 등차수열이여도 인덱스 구성이 다르면 다른 것으로 쳐서 count해줘야 하고 길이가 3이상인 등차수열부터 인정이 되므로 길이가 2인 등차수열의 개수는 0인데, 이렇게 할 경우 인덱스 구성이 다른 것을 카운트하지 못하게 되는 문제가 있었고, 그렇다고 길이가 2인 등차수열의 개수를 count해 버리면 나중에 답을 구할 때, 길이가 2인 것을 어떻게 구별해서 제거할 것인가 하는 문제가 있었는데,
길이가 2인 등차수열의 개수를 count하고 원래 구하는 방식대로 구해나가되, 길이가 2인 등차수열의 개수는 (길이가 2인 그 수열들을 포함하는) 길이가 3인 등차수열의 개수와 같고, 길이가 n인 등차수열의 개수는 길이가 n인 등차수열을 구하기 위해 사용되는 길이가 n-1인 등차수열의 개수의 합이라는 것을 이용해서 결국 길이가 2인 등차수열의 개수부터 길이가 n-1인 등차수열의 개수만 답에 포함시켜 정답을 구할 수 있다.
좀 감격스럽다. 정말 하루 종일 이것만 생각한 것도 아니고 이것 때문에 아무것도 못했다고 해야되나 물론 내가 노력이 부족했지만... 그래도 끈기있게 붙들고 있었던 보람이 있는 것 같다. 비록 내가 생각을 못했지만 남의 코드를 이해했고, 새로운 접근 방식을 깨닫게 되었다. 난 무조건 길이가 n인 경우를 구해야 한다고 생각했는데... 길이가 2인 경우는 경우의 수를 무조건 0으로 둬야 한다고 생각했는데... 발상의 전환인가... 원리를 파고든 것인가.. 여튼 멋지다.
그런데 저렇게 구현해도 틀린다. 아무래도 map이 느려서 그런 것 같다. 이제 unordered_map을 공부할 차례다.... 음 어렵다.
일단 unordered_map에 대해 알지는 못하지만 unordered_map을 사용해서 (사실 사용하는 것도 어려웠다, 그리고 C++11에서 사용 가능) 구현했다.
그리고 깨달은 것이 이 문제에서 map의 기능은 2차원 배열에 대해서 필요한 것이 아니라 1차원 배열에만 필요하다.
댓글 없음:
댓글 쓰기