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

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

1463번: 1로 만들기

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

 

코드

import sys
input = sys.stdin.readline

n = int(input())
d = [0]*1000000

for i in range(2, n+1):
    # 현재의 수에서 1을 빼는 경우
    d[i] = d[i-1]+1
    # 현재의 수가 2의 배수
    if i % 2 == 0 :
        d[i] = min(d[i], d[i//2] + 1)
    # 현재의 수가 3의 배수
    if i % 3 == 0 :
        d[i] = min(d[i], d[i//3] + 1)

print(d[n])

 

 

분석

10을 구할 때, 9의 결과와 3의 결과를 이용해야 한다.

그 전에 구한 결과값을 저장해두었다가 더 큰 값의 결과를 구할 때 이용하는 방법

3과 2로 나누어떨어지지 않는다면 무조건 -1을 해야한다.

d[i] = d[i-1] + 1 로 계산 횟수 +1을 해준다.

i가 2 와 3으로 나누어 떨어지는 경우에는 dp[i](1을 빼는 경우)와 dp[i // 2or3]+1(나누었을 경우) 중 최솟값을 선택한다.

 

NEW

동적프로그래밍이란(DP)?

큰 문제를 작은 하위 문제로 나누어 해결함으로써 전체 문제의 최적해를 구하는 것

동일한 하위 문제가 여러 번 발생할 수 있는데 이를 다시 계산하는 것은 비효율적일 수 있다.

기본원리

1. 주어진 문제를 하위 문제로 나눈다.

2. 각 하위 문제의 해결책을 계산하고 기억한다.

3. 상위 문제의 해결책을 계산할 때 필요한 하위 문제의 해결책을 재사용한다.

 

주로 최적화 문제를 해결하는 데 사용되며, 최단경로문제 / 가장 긴 공통 부분수열 / 베낭 문제 등에 적용

 

처음에 문제를 봤을 때 동적 프로그래밍으로 풀어야한다는 생각이 정말 1도 들지 않았다.

첫 동적 프로그래밍 문제였어서 그런 것 같다. DP 문제도 많이 풀어봐야 문제를 읽고 DP로 풀어야겠다는 생각이 들겠지?