n = 32일 때 2로 5번 나누면 되지만 코드는 6을 출력합니다.
1463번 - 1로 만들기
3으로 나누어진다고 무조건 3으로 나누어야 하는 건 아닐 수도 있습니다.
2로 나누어진다고 무조건 2로 나누어야 하는 건 아닐 수도 있습니다.
//아래는 문제풀이
분할정복을 이용하면 베이스 케이스는 f(1) = 1이고
n % 3 == 0 이면 a = f(n / 3) + 1 아니면 a = MAX
n % 2 == 0 이면 b = f(n / 2) + 1 아니면 b = MAX
c = f(n - 1) + 1
이렇게 3개의 부분문제로 나누어서
f(n) = min{a,b,c}
와 같이 구현할 수 있습니다
댓글을 작성하려면 로그인해야 합니다.
kykbsj 7달 전
문제에 있는 반례는 맞게 나왔습니다
반례 주시면 감사하겠습니다!!