1. 문제

1463번

2. 오답

• 아래 코드는 런타임에러 발생으로 오답 처리 되었다.
• 문제에서는 입력되는 숫자 최댓값을 10^6까지로 했으나,
• 메모이제이션 공간인 dp를 정의할 때 dp[n]을 n의 출력을 정의 했다.
• 그런데 python list는 index를 0부터 처리하기 때문에 dp의 길이는 10^6-1이 되어 런타임에러 발생한 것.

n = int(input())
dp = [0] * 10**6
dp[0] = 0 # 1
dp[1] = 1 # 2 -> 1
dp[2] = 1 # 3 -> 1
dp[3] = 2 # 4 -> 2 -> 1
dp[4] = 3 # 5 -> 4 -> 2 -> 1

for m in range(4 ,n + 1):
    former = [dp[m - 2]]
    if m % 3 == 0: former.append(dp[m // 3 - 1])
    elif m % 2 == 0: former.append(dp[m // 2 - 1])
    dp[m-1] = min(former) + 1
#     print(former)
print(dp[n-1])

• 그러나 dp의 길이를 10^6 +1까지 정의해주었음에도 58%에서 오답처리 되었다.
• index 처리에서 부자연스러운 부분이 있어 엄밀한 정의가 안된 것으로 생각 된다.

3. 정답

• 아래 코드는 정답처리 되었다.
• 위 코드와의 차이점은 dp가 10^6 +1까지 정의 된 것과 index 처리가 잘 되었다.
• bottom-up 구현에 재귀표현을 쓰고 있는데 이 부분이 위 오답과 어떤 차이를 유발하는 지 연구가 필요하다. 예를들어 재귀표현을 사용하지 않고 그냥 dp 공간에서 바로 불러온면 어떻게 되는지?

n = int(input())

dp = [0] * (10**6 + 1)

def one(n):
    if n < 2 : return 0
    if dp[n]: return dp[n]
    for i in range(2, n+1):
        dp[i] = one(i-1) + 1
        if i % 3 == 0: dp[i] = min(dp[i], one(i//3) + 1)
        if i % 2 == 0: dp[i] = min(dp[i], one(i//2) + 1)
    return dp[n]

print(one(n))

4. 추가 연구

• 아래 코드도 정답 처리 되었다.
• 이번 문제 풀이 시 bottom-up 방식을 활용할 때 재귀표현은 크게 영향을 미치지 않는다.
• index 처리, 점화식 표현 및 점화식을 코드로 구현하는 것에 더 신경 써야겠다.

n = int(input())

dp = [0] * (10**6 + 1)

if n > 1:
    dp[1] = 0
    for i in range(2, n+1):
        dp[i] = dp[i-1] + 1
        if i % 3 == 0: dp[i] = min(dp[i], dp[i//3] + 1)
        if i % 2 == 0: dp[i] = min(dp[i], dp[i//2] + 1)

print(dp[n])