[BOJ #1463] 1로 만들기

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

 

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

내가 쓴 코드 1 (틀림)

from sys import stdin; input = stdin.readline
N = int(input())
num = N
cnt1 = cnt2 = 0
while N > 1:
    if N % 3 == 0:
        N //= 3
    elif N % 2 == 0:
        N //= 2
    else:
        N -= 1
    cnt1 += 1

while num > 1:
    if num % 3 == 0:
        num //= 3
    else:
        num -= 1
    cnt2 += 1

print(min(cnt1, cnt2))


'''
반례
40 -> 5
41 -> 6
'''

 

내가 쓴 코드 1 (맞.)

from sys import stdin; input = stdin.readline
N = int(input())

# dp : 최소 연산 횟수
dp = [0] * (N + 1)

# bottom-up (거꾸로)
for i in range(2, N + 1):   # dp[1] = 0 이니까 dp[2] 부터 시작.
    dp[i] = dp[i-1] + 1     # i - 1 : 1 빼기 -> cnt += 1

    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i // 3] + 1)  # i // 3 : 3 나누기 -> cnt += 1
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i // 2] + 1)  # i // 2 : 2 나누기 -> cnt += 1

print(dp[N])

간단해보이는 문제와 간단해보이는 코드에 비해 간단하지 않았던 문제.. 코드1 처럼 써서 풀었었는데 얄짤 없이 틀렸다길래 반례를 뒤져봤는데, 40, 41이 반례였다.. 그래서 깨우쳤지 저렇게는 해결할 수 없겠다. 진짜 모든 경우 다 계산해야 되는 문제다..를. 그래서 혼자 해결하기를 포기하고 이 문제를 통해 DP 를 공부하자! 싶어서 DP 설명되어있는 블로그를 찾아보는데 첫 예제 문제로 이 문제가 나온것이다.. 그래서 열심히 30분동안 눈싸움하면서 내가 이걸 이해를 해버렸다! 근데 런타임 에러가 뜬 것은,, 처음 dp 리스트를 [0] * int(1e6) 이라고 했더니 너무 컸나보다.. 아니 입력값이 거기까지 나온다면서요...! 암튼 그 부분 고치니까 패씅~!!!

알고리즘 분류? 들의 개념... 진짜 모르겠다.. ㅠㅜ 이렇게 알고리즘 문제 풀면서라도 조금씩 공부해야징! 다들 ㅎㅇㅌ ~

 

제출 결과