[Python] 백준 1463 1로 만들기 | DP

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

1463번: 1로 만들기

 

 

문제 해결 포인트

- 전형적인 다이나믹 프로그래밍 문제이다.

- 각 인덱스 번호를 구하기 위해서 필요한 최소 연산을 저장할 리스트를 입력 받은 N 크기로 생성.

- 다이나믹 프로그래밍

    바텀업(BottomUp) : 반복문

    탑다운(TopDown) : 재귀

 

바텀업 방식이 스택 크기 제한으로부터 자유로움으로, 처음 연산을 저장하여 이후 동일한 연산 발생시

이를 사용하여 중복 연산을 피할 수 있다.

 

- 최종적으로 1을 만드는 프로그램이므로 2부터 구하려는 n까지 각 수를 위한 최소 연산을 구한다.

- 즉 2라면 -1을 빼는 연산과 2로 나누는 연산을 하면 모두 한 번의 연산으로 가능하므로

  최종적으로 dp[2]에 1이라는 값이 입력된다.

- 이를 연쇄적으로 수행함으로써 dp[n]에는 n을 구하기 위한 최소 연산의 값이 저장된다.

 

작성 코드

 

n = int(input())
dp = [0]*(n+1)  # 인덱스 번호를 위해서 필요한 최소 연산 횟수 저장

for i in range(2, n+1):  # 바텀업 방식
	dp[i] = dp[i-1] + 1  # -1 1회 수행
    if i % 3 == 0:
    	dp[i] = min(dp[i//3] + 1, dp[i])  # 3의 배수라면
    if i % 2 == 0:
    	dp[i] = min(dp[i//2] + 1, dp[i])  # 2의 배수라면
        
print(dp[n])

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚