백준 - 1로 만들기(Python)

백준 - 1로 만들기(Python)

 

www.acmicpc.net/problem/1463

1463번: 1로 만들기

문제 해석:

위 문제는 다이나믹 프로그래밍을 대표하는 문제이다.

 

다이나믹 프로그래밍은 어려운 개념은 아니고 필자의 경험대로 풀어쓰자면 긴 수행시간을 줄이거나 메모리를 효율적으로 사용해야 할 경우에 '점화식'과 같은 방법의 활용으로 해결하는 방법이다.

 

필자가 풀어본 1로 만들기 문제중에 그리디 문제도 있었는데, 동전 거스름돈 문제(그리디)처럼 큰수부터 나누면 최솟값이 당연하게 나오지 않지 않나?라고 생각할 수도 있다. 하지만 큰 수로 나누다가 값이 나눠지지 않아 1로 계속 빼야하는 경우는 오히려 최솟값이 아닌 최대값에 가까운 수가 나올 수가 있다.

 

이와 같이 1로 만드는데 많은 조건이 붙은 것은 보통 다이나믹 프로그래밍을 이용하면 된다.

 

우리는 d라는 리스트를 만들어 볼 건데, '이는 1까지 만드는데 연산되는 최소한의 값을 담는 리스트'이다.

 

예를 들어 d[1]의 1까지 만드는데 연산되는 최소한의 값은 0이다. 1은 1이기 떄문에 연산이 필요없기 때문이다.

d[2]는 1까지 만드는데 2가지 방법이 존재한다.

 

 1. 1을 뺀다.

 2. 2로 나눈다. 

d[2]는 두개의 연산된 값이 모두 같기 때문에 둘 중 하나를 택해서 d[2]에 넣으면 된다.

 

하지만 d[3]은 어떨까?

  1. 1을 뺀다

  2. 3으로 나눈다.

 

1번을 수행한다면 

  값이 2가되기 때문에 또 d[2]과정을 해야한다. 총 2번의 연산이 이루어진다.

 

2번을 수행한다면

  곧바로 1이되어 연산이 1번만 이루어진다.

 

그렇다면 두개의 연산 중 최소값을 d[3]에 담으면 된다는 것을 알 수 있다.

 

d[10]을 구하려면 어떠한 원리로 계산이 되는 걸까?

 

1을 먼저뺴고, 3으로 나누고, 3으로 나눈다.

d[10] = d[10-1]+1 --> d[9] = d[9//3]+1 --> d[3]  = d[3//3] +1  ------->result = 3

 

 

이를 코드로 작성해보면 이렇다.

 

x = int(input())

d = [0]*100000001

d[1] = 0
for i in range(2,x+1):
  d[i] = d[i-1] +1
  if i%2==0:
    d[i] = min(d[i], d[i//2]+1)
  if i%3==0:
    d[i] = min(d[i], d[i//3]+1)

print(d[x])