[python]백준 1463번: 1로 만들기(DP)

# 1463 1로 만들기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

코드

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

📝 풀이

문제에서는 1로 만들기 위한 세 가지 가정을 제시했다.

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

1로 만들기 위한 가장 빠른 방법은 숫자를 크게 줄이는 것이다. 그렇기 때문에 1번이 적용되면 1번을 실행하고, 2번이 적용되면 2번을 실행하면 되나 생각하게 된다. 하지만 10의 경우에는 2번 조건을 먼저 실행시키는 것이 아닌  -1을 먼저 하고 3을 나누는게 가장 빠른 방법이다.

10 -> 5 ->  4 ->  2 -> 1 4번

10 -> 9 -> 3 ->  1 ->  3번

다양한 경우를 고려해야 하므로 DP를 이용해서 min값을 찾아줘야 한다.

🔓 코드 뜯어보기

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

구해야 하는 값 n을 받고, dp = [0] * (n+1)을 해준다. n+1 이라고 한 이유는 1번째 수는 사실 dp[1]이 아니고 dp[2]이기 때문에 계산하기 편하게 dp[1]을 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)
# dp = [0, 0, 1, 1, 2, 3, 2, 3, 3, 2, 3]
print(dp[n])

반복문 범위를 2 ~ n+1가지로 반복시켜준다. 

dp[i] = dp[i-1] +1 코드가 쉽게 이해가지 않는데

예를 들면 dp[3] = dp[2] + 1 이라고 하면, 3에서 1을 빼는 1회 연산을 통해 2가 되므로  dp[2] + 1은 3에서 1을 빼서 2가 되고, dp[2] (2에서 1이 되는데 필요한 최소 연산 횟수)를 더해준 것이다.

그리고 나서 i가 2로 나누어지면 dp[i] = min(dp[i], dp[i//2] +1)를 통해 작은 값을 저장시켜준다.

1을 더하는 것은 dp는 결과가 아닌 계산한 횟수를 저장하는 것이기 때문이고, 그렇다 dp[i]에는 왜 안 더하냐고 한다면 이미 앞에서 1을 더해준 이력이 있기 때문이다.

동일하게 i가 3으로 나누어질 때 로직도 작성해준다. 여기서 중요한 점이 각각 if문을 사용해야 연산을 다 거칠 수 있다.