jqp5548   1년 전

dp문제인건 알지만, 대충 떠오른대로 적다보니 그리디 알고리즘으로 대충 나온것 같은데, 

틀렸다고 나옵니다.

이유가 뭔가요?

lcr7324   1년 전

반례입니다.

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회)

그리디로는 안 풀리는 문제입니다.

osh1795   1년 전

반례 input: 16 / 정답: 4 / 출력: 5

3k +1꼴 일 때, 1을 빼고 3으로 나누는데 2로 나누는 것보다 항상 적게 걸린다고 할 수 없을 거 같습니다.

10의 경우 2로 나누는 연산보다 1을 빼고, 3을 2번 나누는게 더 적게 걸리지만(10-9-3-1 4회/ 10-5-4-2-1 5회),

16의 경우 2로 계속 나누면 4회(16-8-4-2-1), 작성하신 코드는 5회(16-15-5-4-3-1) 필요하므로 2로 먼저 나누는게 더 적게 걸립니다.

만약, 그리디로 푸신다면 흠... 3n +1일경우, 3n을 소인수분해해서 3의 지수를 파악하는 등의 작업으로 두 연산(line 26, line29)중 어떤게 더 나은지 파악이 필요할 거 같네요.. 정확히는 잘 모르겠습니다.

댓글을 작성하려면 로그인해야 합니다.