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

[이코테] 문제1 - 1로 만들기(217p)

(한줄평) 평소였으면 최소값을 구하는 문제니 BFS로 해결 했을테지만 전형적인 다이나믹 프로그래밍 문제! 추후 복습이 꼭 필요한 문제

 

풀이 시간: 40분 이내

1) 문제 해결 아이디어

정수 x가 주어졌을 때, 연산 4개를 적절히 사용해 1을 만드는데 사용되는 연산의 최솟값을 구하는 문제다. 

a. x가 5로 나누어 떨어지면, 5로 나눈다

b. x가 3으로 나누어 떨어지면, 3으로 나눈다

c. x가 2로 나누어 떨어지면, 2로 나눈ㄴ다

d. x에서 1을 뺀다

 

<다이나믹 프로그래밍의 조건>

1. 최적 부분 구조

큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제 해결O

2. 중복되는 부분 문제

동일한 작은문제를 반복적으로 해결해야 함

 

Q. 이 문제를 다이나믹 프로그래밍으로 풀 수 있는 이유는?

책 예제 입력처럼 x가 26이라면 이런 식으로 동작을 하게 된다

이 문제는 큰 문제를 작은 문제로 나눌 수 있다.  위와 같이 4가 2번 호출되는 것을 알 수 있는데. 즉, 동일한 작은 문제를 반복적으로 해결해야한다는 것이다. 위 2조건을 모두 만족하므로 다이나믹 프로그래밍을 이용하여 해결이 가능하다.

 

Q. dp 테이블(d)의 역할은?

일단 bottom-up 방식에서 값을 기록해 놓기 위해 dp테이블을 사용해야하는데 정수 x가 1이상 30,000이하의 범위이므로 30001의 크기로 0으로 초기화햐여 생성해야한다.

dp 테이블에 기록할 값은 현재값(i)가 되기까지 최소 연산횟수이다. 이게 바로 중요 포인트!!

 

Q. 코드를 짤 때 연산의 조건을 d, c, b, a 순서로 하는 이유는?

처음에는 아무생각없이 책에 나온 조건 a, b, c, d 순서대로 코드를 짰는데 이렇게 되면 문제가 생긴다.

이 문제는 상향식으로 풀기 때문에 x→1이 아닌 1→x 를 만드는 코드다.

그러므로 더 작은 값을 만드는 순서로 값을 기록해야 한다!!

 

2) 소스코드

x = int(input()) 
d = [0] * (30001)  # dp 테이블 초기화

# bottom-up
for i in range(2, x + 1):
  # 4. x에서 1을 뺌
  d[i] = d[i - 1] + 1
  # 3. x가 2의 배수이면 2로 나눔
  if i % 2 == 0:
    d[i] = min(d[i], d[i // 2] + 1)
  # 2. x가 3의 배수이면 3으로 나눔
  if i % 3 == 0:
    d[i] = min(d[i], d[i // 3] + 1)
  # 1. x가 5의 배수이면 5로 나눔
  if i % 5 == 0:
    d[i] = min(d[i], d[i // 5] + 1)

print(d[x])  # x에서 1을 만드는 최소 연산 횟수