dp[1000000]에 접근하기 위해서는 dp의 크기가 최소 1000001이어야 합니다.
그리고 이 코드는 dp라고 부르기 어렵습니다. 현재 N을 보고 최적이 되는 다음 N을 직접 골라 그 방향으로만 나아가기 때문입니다. dp가 되려면 모든 가능성을 열어두고 다 해본 뒤 그 중 최적을 고르는 형식이 되어야 합니다. 3으로 나누어 떨어진다고 해서 바로 3으로 나누는 게 최적이라는 보장도 없고, 1을 뺀 뒤 3으로 나눌 수 있다고 해서 그렇게 하는 게 최적이라는 보장도 없고, 2로 나누어 떨어진다고 해서 2로 바로 나누는 게 최적이라는 보장도 없습니다. 그저 추측에 불과합니다.
kcsoo1234 2년 전
야밤에 질문 올립니다...
예시나 다른 케이스들도 다 정답이 나오는데 왜 자꾸 틀리다고 나올까요? 반례가 궁금합니다