Algospot :: TRIPATHCNT 계속 오답이었던 이유.

정말 어이없는 실수를 하고 말았다.

더 큰 문제는 그런 실수를 하고도 한동안 그 실수를 깨닫지 못했다는 것이다.

이 문제에서 숫자의 합이 가장 큰 경로의 개수를 구하기 위해서 일단 각 점에서 출발하는 경로중 숫자의 합의 최대값을 dp로 구하고 그것을 이용해서 각 점에서 출발하는 숫자의 합이 최대가 되는 경로의 개수를 구하였다.

다음 점을 선택할 때, 선택할 점은 바로 아래 혹은 오른쪽 대각선 방향 아래로 2가지 점밖에 없다. 그 두 가지 점중에서 어느 점으로 가야 숫자의 합이 최대가 되는 경로인지 찾아서 만약 둘다 똑같다면 두 점에서 출발하는 (숫자의 합이 최대가 되는)경로의 개수를 더하고, 다르다면 그 숫자의 합이 최대가 되는 경로를 갖고 있는 점을 선택해서 그 점에서 출발하는 경로의 개수를 택하면 되는 것인데...

나는 다음 두 점이 다를 경우 숫자의 합이 최대가 되는 경로를 갖고 있는 점을 선택하지 않고, 그냥 경로의 개수가 더 큰 점을 선택하였다.
근데 이게 정말 알아차리기가 힘들었다. 아무리 봤지만 알아차리지 못했고, 정답 코드를 실행해보고 비교해보면서도 한동안 이해 못했다...

그래도 결국 이해해서 다행이다.