백준 1463번- '1로 만들기' (PYTHON 풀이)

문제:

 

입력값을 받고 그 입력값을 나누기, 빼기로 1을 만들어야하는데 가장 최소한의 횟수만 사용해서 1을 만들 때 그 횟수를 출력하면 되는 문제이다.

 

풀이:

N = int(input())
count = 0

while N != 1:
    if N % 3 == 0:
        N = N // 3
        count += 1
    elif N % 2 == 0:
        N = N // 2
        count += 1
    else:
        N -= 1
        count += 1
print(count)

처음에 '최소한' 부터 구현하려고 하면 어려울 것 같아 일단 차근차근 순서에 맞게 작성해봤다. 횟수 제한 없이 1로 만드는 횟수를 그냥 구하기만 한다면 다음과 같이 작성하면 될 것이다.

하지만 우리는 이 문제를 풀기 위해 '최소한'이라는 횟수 조건을 기억하고 있어야 한다. 결국엔 DP를 사용해야 하는데 DP란 큰 문제를 작은 문제들로 쪼개서, 각 작은 문제의 정답을 미리 저장해두고 그걸 재사용해서 전체 문제를 빠르고 효율적으로 푸는 방법이다.

아무때나 쓰는 방법은 아니고 피보나치 수열이나 해당 문제처럼 겹치는 부분이 있을 경우 사용하면 좋다.

N = int(input())

dp = [0] * (N + 1)

for i in range(2, N + 1):
    dp[i] = dp[i - 1] + 1

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

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

print(dp[N])

필자도 DP를 이번에 처음 알게 된 거라 어떻게 풀어야할지 감이 안와서 서치를 통해 풀었다.

일단 이번 코드의 핵심은 dp[i]를 '정수 i를 1로 만드는 데 필요한 최소 연산 횟수'로 정의하는 것이다. dp[1]은 이미 1이므로 0이고, dp[2]부터 dp[N]까지 값을 채워 나가면 마지막에 dp[N]이 정답이 된다. 좀 더 설명을 하자면 배열의 각 자릿수는 자리에 해당하는 값을 1로 만든는 최소 연산 횟수이다. dp[2]는 2를 1로 만드는 최소 연산 횟수, dp[3]은 3을 1로 만드는 최소 연산 횟수이다.

i를 1로 만드는 최소 연산을 생각하면, i에 도달하기 직전의 상태는 항상 세 가지 중 하나이다: i-1, i/2(2로 나누어 떨어질 경우), i/3(3으로 나누어 떨어질 경우). 따라서 dp[i]는 dp[i-1] + 1, dp[i//2] + 1, dp[i//3] + 1 중 가능한 값들 중에서 가장 작은 값이 된다. 이를 정리한 식은 다음과 같다.

dp[i] = min( dp[i-1] + 1, (i%2==0) → dp[i//2] + 1, (i%3==0) → dp[i//3] + 1 )

이 규칙을 기반으로 2부터 N까지 순서대로 dp 배열을 채우는 방식으로 구현하면 된다. 이때 dp는 [0] * (N+1)로 초기화해두고 실제로 의미 있게 사용하는 값은 dp[1]~dp[N]이다. dp[0]은 인덱스 정렬을 편하게 하기 위한 더미 공간이며 계산에는 사용되지 않는다.