[Python] 백준 1463 1로 만들기 - 동적 계획법 (DP)

백준 홈페이지 문제와 개인적인 풀이를 작성한 글입니다.

 

백준문제 - 1463 : 1로 만들기

1463번: 1로 만들기

---

 

문제

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

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

정수 N 이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1 을 만들려고 한다.

연산을 사용하는 횟수의 최솟값을 출력하시오.

 

입력

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

 

 

출력

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

 

예제 입력 1	예제 출력 1
2	1

 

예제 입력 2	예제 출력 2
10	3

 

문제를 풀기 전에

입력 값의 한계 값을 주의 했다. ( 10^6 )

왜냐하면, 너무 값이 크다면 DP 로 풀었을 때 비효율 적이라고 생각했다.

 

코드 - 최솟값 추출 없이 작성 (당연하게 오답)

import sys
input = sys.stdin.readline

n = int(input())
result = 0

while n != 1:
  
  if n % 2 == 0 :
    n = n // 2
  elif n % 3 == 0:
    n = n // 3
  else:
    n -= 1

  result += 1

print(result)

 

만약 10 을 입력한다면?

위 처럼 최솟값을 생각 안하고 작성을 한다면 답이 틀린다. 

 

오답
10 -> 5 -> 4 -> 3 -> 1 
출력 : 4

정답
10 -> 9 -> 3 -> 1
출력 : 3

 

최솟값을 본 순간 부터, 다른 방식으로 풀어야 한다.

그러면, 두 가지의 min 값을 구해서 출력해 주면 될 것 같다는 생각이 들었다.

입력한 수를 X 라고 가정해보자.

min( (X-1) , (X // 2 or X//3) ) 을 비교해서 코딩하면 되겠다 라는 느낌이 들었다.

 

코드 - 정답

import sys
input = sys.stdin.readline

n = int(input())

list = [0] * (n + 1)

for i in range(2, n + 1):
  list[i] = list[i - 1] + 1

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

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

print(list[n])