kykbsj   7달 전

문제에 있는 반례는 맞게 나왔습니다

반례 주시면 감사하겠습니다!!

skuru   7달 전

n = 32일 때 2로 5번 나누면 되지만 코드는 6을 출력합니다.

kangjijoon   7달 전

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}

와 같이 구현할 수 있습니다

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