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

 

• 문제 설명

다이내믹 프로그래밍의 가장 기본적인 문제이다. 입력으로 받은 정수 x를 5로 나누기, 3으로 나누기, 2로 나누기, 1을 빼기 이 4가지 경우의 수를 조합해 최소한의 연산으로 1로 만드는 연산의 횟수를 출력하면 된다. 

 

• 문제 코드

X = int(input())
dp = [0] * (X+1)

for i in range(2,X+1):
    dp[i] = dp[i-1]+1 # 1 뺏을 때

    if i%2 == 0:
        dp[i] = min(dp[i],dp[i//2]+1) # 2로 나누었을 때
    if i%3 == 0:
        dp[i] = min(dp[i],dp[i//3]+1) # 3으로 나누었을 때
    if i%5 == 0:
        dp[i] = min(dp[i],dp[i//5]+1) # 5로 나누었을 때
print(dp[X])

 

일단 입력으로 받은 수만큼을 dp테이블에 저장해야 하니 X+1만큼의 리스트를 0으로 초기화해준다. 이때 인덱스는 1부터 사용할 거라서 X+1만큼의 리스트를 만들어준다.

그리고 위 4가지의 경우의 수를 모두 구해줄 것이다. 모든 경우의 수를 구하여 최솟값을 출력해야 하니 elif문으로 사용하면 안되고 모두 if문으로 경우의 수를 구해주어야 한다.

 

코드를 하나 하나 살펴보겠다.

1. dp [i] = dp [i-1]+1

이는 현재의 수에서 1을 빼는 경우이며, 1을 빼면 연산 횟수가 1 증가하니 이전의 값에서 1을 더해준다.

 

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

이는 현재의 수가 2로 나누어 떨어지는 경우이며, dp [i]를 dp [i]와 dp [i//2]+1중에서 최솟값으로 바꿔준다. 이때 비교 대상인 dp [i]는 바로 윗 줄에서 1을 뺏을 때의 연산 횟수가 저장되어 있다. 그리고 dp [i//2]+1은 2로 나누어지는 경우이므로 연산 횟수를 1을 더해주는 것이다. 이 둘 중에 최솟값으로 dp [i]에 저장해 둔다.

위와 같은 과정으로 3, 5로 나누어지는 경우를 따져주면 된다.

 

처음에는 어떻게 할지 감이 안 왔는데 조금씩 풀어보니 어떻게 접근해야 하는지는 느낌이 온다. 먼저 dp테이블을 만들 생각을 하고 점화식을 떠올려서 반복문을 통해 이를 어떻게 적용할 지에 대해 생각을 하는 느낌으로 접근하면 좋을 것 같다.

 

• 관련 문제

 

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

1463번: 1로 만들기