반례입니다.
40 > 39 > 13 > 12 > 4 > 3 > 1 (6회)
40 > 20 > 10 > 9 > 3 > 1 (5회)
그러면 1을 빼고 3으로 나누는 것 말고, 그냥 3으로 나눌 수 있으면 우선 3으로 나누는 그리디는 안되냐는 질문으로 이어질 수 있습니다.
하지만 이번에도 반례가 있습니다.
642 > 214 > 107 > 106 > 53 > 52 > 26 > 13 > 12 > 4 > 2 > 1 (11회)
642 > 321 > 320 > 160 > 80 > 40 > 20 > 10 > 9 > 3 > 1 (10회)
그리디로는 안 풀리는 문제입니다.
jqp5548 1년 전
dp문제인건 알지만, 대충 떠오른대로 적다보니 그리디 알고리즘으로 대충 나온것 같은데,
틀렸다고 나옵니다.
이유가 뭔가요?