[백준][python]1463 1로 만들기

문제

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

소스코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":  
    n = int(input())
    dp = [0] * (n+1)

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

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

설명

DP 를 이용해서 풀어야하는 문제이다.

dp를 공부하는데 도움이 된 아래 블로그에서 제시한 dp를 사용하기 전에 거쳐야 하는 과정을 통해 해결방법을 확인해보자

https://hongjw1938.tistory.com/47

 

1. DP 로 풀 수 있는 문제인지 파악한다.

bottom - up 방식으로 문제 해결 가능.

작은 문제를 해결하여 큰 문제를 풀 때 사용할 수 있다.

 

2. 문제의 변수 파악

구해야하는 값은 "연산를 몇 번 했는지" 이다.

각 숫자에서 최소 연산 수를 메모이제이션한 후 + 1 한 값이 내가 구하고자 하는 값이다.

 

예를 들어, dp[3] 에서 1로 가는 연산의 가장 작은 값을 구하려면, 

dp[2] 의 값에서 + 1 을 한 dp[2] + 1 이거나,

dp[1](3//3) + 1 을 한 값 중에 작은 값을 선택하면 된다.

 

+ 1 은 3이 되기 위해 무조건 카운팅이 되야하는 숫자이다. 어떤 숫자에서 3이 되려면 연산을 무조건 해야하니까요

 

3. 변수 간 관계식 만들기 : 점화식

dp[n] = min(dp[i//2] + 1,dp[i//3]+1,dp[n-1] + 1) 

 

4. 메모하기

구한 값들은 dp에 저장하였다.

 

5.기저 상태 파악하기

가장 작은 문제의 상태를 확인한다. 

dp[1] = 0 : 1인 경우 연산이 필요 없다.



가장 작은 문제의 상태는 '1'인 경우만 사전 초기화가 가능하므로 dp를 모두 0으로 초기화 한다.

반복문은 2부터 돌려서 구현을 진행한다.

 

6.구현하기

bottom-up 방식으로 반복문을 사용하여 구현해준다.

 

top-down 인 경우 반례가 발생함

예를 들어 n = 10인 경우 ,

10 > 5 > 4 > 2 > 1 인 경우가 발생하기 때문에 안된다. 

 

후기

- 그리디로 푼다면 큰 수에서 계속 나눠서 가장 빨리 나누는 것이 1로 도달할 수 있지만 반례가 있고 시간 초과가 난다. 그래서 바로 dp 로 구현해보았다. 

- 문제에서 1 , 2 , 3 조건의 순서를 줘서 1을 빼는 경우를 가장 마지막에 했는데 이러면 제대로 답이 나오지 않는다.

1을 빼는 경우는 무조건 체크할 수 있는 연산이므로 가장 처음에 둔 후 나머지를 체크해준다. 어짜피 나중에 교체된다.

알고리즘 - Dynamic Programming(동적 계획법)

알고리즘 - Dynamic Programming(동적 계획법)

알고리즘 - Dynamic Programming(동적 계획법)