[다이나믹 프로그래밍] 1463번 - 1로 만들기

[백준] 1463번 - 1로 만들기

(한줄평) 전에 풀었던 문제와 유사하지만 생각보다 시간이 좀 걸렸던 문제!

유사 문제: https://hseungyeon.tistory.com/285

[다이나믹 프로그래밍] ▲ 문제1 - 1로 만들기(217p)

 

풀이 시간: 20분 이내

1) 문제 해결 아이디어

정수 X(1 <= X <= 10**6)에서 3가지 연산을 사용하여 1을 만드는데 필요한 연산의 사용 횟수의 최솟값을 구하는 문제다.

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

이 문제는 X→1로 만드는 문제지만 1→X로 만드는 문제로 치환할 수 있다.

 

<점화식>

Q. "1을 더하기" 부분만 최솟값을 대입하지 않고 바로 값을 넣는 이유는?

일단 처음 값을 넣을 때는 0으로 값이 초기화 되어있기 떄문에 0이 최솟값이 되는 문제가 발생하므로 첫 값은 최솟값이 아닌 바로 그 값을 넣어야 한다!! 

그래서 1연산 값은 바로 넣고 2, 3은 각각 자기 자신값과 연산한 값 중 최솟값을 갱신한다.

주석한 부분은 점화식 그대로 코드를 짜는 방식인데 시간 효율은 좀 더 떨어진다.

 

2) 소스코드

n = int(input())  # 1이상 10**6이하 정수
d = [0] * (n + 1)  # i를 만들기 위한 최소 연산 사용 횟수

for i in range(2, n + 1):
  # 1. 1을 더하기
  d[i] = d[i - 1] + 1
  # 2. 2를 곱하기
  if i % 2 == 0:
    d[i] = min(d[i], d[i//2] + 1)
  # 3. 3을 곱하기
  if i % 3 == 0:
    d[i] = min(d[i], d[i//3] + 1)
  '''
  a = d[i-1] + 1
  b, c = a, a
  if i % 2 == 0:  b = d[i//2] + 1
  if i % 3 == 0:  c = d[i//3] + 1
  d[i] = min(a, b, c)
  '''
print(d[n])  # n을 만드는데 필요한 연산 최소 횟수