12969번 ABC - memoization을 이용한 문자열 구하기에서...

처음엔 백준님의 정답 코드를 이용해서 모든 가능한 입력값에 대한 답을 구한 후 비교를 하려고 했는데, 일단 -1이 나오는 경우는 비교를 했는데 똑같았다. 그 외에는 답이 다르기 때문에...(special judge) 그래서 결국 내가 직접 내 코드의 출력 값이 맞게 나왔는지 검증하는 코드를 짜서 비교해본 결과 나온 반례가

13 40 -> ACBBACCCCCCCC 였다.
확실히 틀렸다.

음... 그래서 분석을 하는데 정말 힘들었다. 내 생각에 따르면 절대 저렇게 답이 나오면 안되는데... 직접 출력도 해보고 그려보기도 하고 했는데도, 점점 범위를 좁혀나가면서 알듯 말듯 했는데, 결국 알아냈다!

바로 단순히 재귀가 아닌, dp를 이용하기 때문이다.
정확히는 memoization을 이용해서 한 번 살펴본 것은 더이상 살펴보지 않기 때문에, 문자열이 잘못 나오는 경우가 발생한다...

더 자세히 기록하자면... 일단 memoization때문에 한 번 살펴본 것은 다시 안 보는데, 예를 들어 처음에 dp(3, 2, 1, 2)에 대하여 'ABB'가 저장되었다고 하자.
그럼 이제 더이상 dp(3, 2, 1, 2) 인 부분은 의심하지 않고 넘어가게되는데, 문제는 'ABB'이 것이 유지가 안된 다는 것이다. 배열을 전역변수로 놓고 계속 업데이트 되기 때문에 중간에 다른 과정을 거쳐 'ABB'가 'BCA'로 바뀌었더라도, memoization때문에 그 부분은 살펴보지 않게 되는 것이다. 물론 그냥 재귀라면 다시 살펴보기 때문에 옳은 값이 나온다.

근데 이렇게 원인은 알았는데, 이제 이 것을 어떻게 수정해야할지도 문제다...

일단 아까도 중간에 잠깐 해보았지만, 다시 수정한 것이

이 부분에서, if, if, if를 if, else if, else if로 바꿔서 되는 경우 하나만 보게 하는 것인데, 이렇게 실행해보니 일단 내가 만든 검증 코드에서는 맞는 것으로 나온다.

그래서 생각해보니 ...지금 문제가 전역변수인 어레이가 수정되어도 안보게 되는 것인데,
위와 같이 수정할 경우, 어레이가 수정될리가 없다. 왜냐하면 true이면 그걸 쓰기 때문이다.

다시 설명하자면, 처음 코드에서는 세 번 dp를 호출하면서, 만약 첫 번째 dp에서 true인 것을 memoization하고 그 부분은 array를 더 이상 안 보게 되는데, 세번 째 dp에서 만약 그 memoization인 부분을 만나면 당연히 true이므로 array는 당연히 맞겠지 하고 넘어가지만, array는 전역변수라 중간에 다른 dp들에 의해 바뀌었을 수 있다!!!

하지만, 위와 같이 수정할 경우, 되는 것 하나만 보기 때문에, 되는 것을 다보는 처음 코드처럼 array의 수정이 일어나지 않을 것이다!

한 번 제출해봐야겠다!
맞았습니다! 가 떴다...
시간을 많이 소비하긴 했지만 그래도 이렇게 문제점을 완전히 파악하고 고쳐서 제출해서 다행이다.