[백준] 1463번 문제 (1로 만들기) 파이썬(Python) 풀이

n = int(input())
dp = [0] * (n + 1)

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

처음에는 dp의 개념이 없었기 때문에 풀지 못 한 문제였다.

대부분의 사람이 그리디 문제인 줄 알고 그리디식으로 접근하다가 틀리는 것 같았다.

 

핵심은 dp에 항상 해당 숫자를 최소한의 연산으로 1로 만든다 가정했을 때,

그 연산이 걸린 횟수를 저장하는 것이다.

 

숫자 2가 1이 되는데 필요한 최소 연산은 1번이다. 

2로 나누거나 1을 빼면 된다.

 

숫자 3이 1이 되는데 필요한 최소 연산도 1번이다.

3으로 나누면 된다.

 

숫자 4가 1이 되는데 필요한 최소 연산은 2번이다.

2로 두 번 나누거나, 1을 빼고 3으로 나누거나 하는 등의 방법이 있다.

 

우선 1을 빼는 방법을 제외하고 2로 나누거나 3으로 나누는 횟수를 어떻게 구할까 생각해보면,

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)

위와 같이 나타낼 수 있는데, 처음에는 와닿지 않을 수 있다.

 

숫자 6을 예로 들어보면,

첫 번째 if문의 조건이 맞기 때문에 해당 코드가 동작하는데, 그렇다면 아래와 같이 나타낼 수 있다.

dp[6] = min(dp[6], dp[6 // 3] + 1)

dp[6]에 현재 dp[6]에 들어있는 값과 dp[6 // 3] + 1 값 중 작은 값을 할당한다.

 

왜 그럴까?

 

천천히 생각해보면 알 수 있을 것이다.

우선 dp[6]에 dp[6]을 할당하는 것은 6이 2로도 나눠지고 3으로도 나눠지기 때문에 이미 dp[6]에 들어가 있는 값이

dp[6 // 3] + 1 보다 작을 수 있기 때문이다.

 

또한 dp[6]에 dp[6 // 3] + 1 를 할당하는 이유는

우선 6 // 3을 하면 2가 나온다. (몫을 구함)

그러면 dp[2]에 값이 나올 것이고 dp[2]에는 2를 1로 만드는 최소한의 연산 횟수인 1이 들어가 있을 것이다.

그렇다면 숫자 6은 숫자 2보단 최소한 연산을 한 번 더 하는 것이므로 +1 을 해주는 것이다.

 

아래 코드도 위와 마찬가지의 논리도 동작한다.

if i % 2 == 0:
    dp[i] = min(dp[i], dp[i // 2] + 1)

그렇다면 여기서 두 가지 정도의 궁금증이 생길 수 있다.

 

1. 1을 빼준 연산은 어디있지?
2. if, else문이 아닌 if문 2개인 이유가 뭐지?

 

우선 첫 번째 궁금증은 위에서 잠깐 무시하고 지나간 코드에서 알 수 있다.

dp[i] = dp[i - 1] + 1

for 문에서 if문 2개를 통과하기 전에 dp[i]에 대하여 dp[i - 1] + 1을 할당해준다.

이게 무슨 뜻일까?

 

dp[i]는 if문 두 개를 거치기 전에 dp[i - 1] 보다 1이 큰 값을 할당해준다.

만약 i가 3이라고 했을 때

 

dp[3]은 dp[2]의 값 + 1이 되는 것인데 dp[2]의 값은 1이므로 dp[3]은 2가 된다.

이게 뜻하는 바는,

숫자 2의 최소 연산 횟수보다 숫자 3의 최소 연산 횟수가 숫자 2보다는 한 번 더 많을 것이라고 가정하는 거라고 생각하면 된다. 이게 바로 1을 뺀 연산이라고 생각하면 된다.

 

숫자 2보다 숫자 3이 더 크니 dp[3]에 dp[2] + 1을 할당하는 것이다.

 

그리고 if문 조건에서 더 작은 숫자가 되면 그것이 최소 횟수가 되는 것이고 아니면 dp[3]에 들어간 값이 제일 작은 값이 될 것이다. 해당 숫자 -1의 최소 연산 횟수의 1을 미리 더함으로써 1을 뺀 연산의 효과를 얻을 수 있는 것이다.

 

두 번재 궁금증은 위보다 훨씬 이해하기 쉬울 것이다.

왜 if, else 문이 아니고 if문이 두 개일까?

 

사실 좀만 생각해보면 당연한 것이라고 생각될 수 있다.

나누기 3이 최소 횟수로 만들 수 있는지 나누기 2가 최소 횟수로 만들 수 있는지, 사실 바로 알 수 없다.

그렇기 때문에 두 if문을 거칠 수 있게 만들어서 두 개 중에 최소한의 숫자가 되는 경우를 dp에 할당하면 된다.