[🤷‍♀️ 백준] 1463번. 1로 만들기 (PYTHON)

📌

문제 및 문제설명

www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

📌

답

n = int(input()) #1
a = [0 for _ in range(n+1)] #2 

for i in range(2, len(a)): #3
  a[i] = a[i-1] + 1
  if i%3 == 0:
    a[i] = min(a[i], a[i//3]+1)
  if i%2 == 0:
    a[i] = min(a[i], a[i//2]+1)
    
print(a[n])

다이나믹 프로그래밍으로 푸는 문제!

 

1. input을 통해 입력값을 받는다.

 

2. n+1만큼 크기의 리스트를 만들어준다! 이 리스트엔 인덱스 숫자가 1이 되기까지의 최솟값이 저장된다. 

(예를 들어 인덱스가 10이면, 10이 1이 되기까지의 최솟값인 3이 저장된다.) 

그렇기 때문에 n+1만큼의 크기를 만들어줘야 한다.

 

3. for문을 이용하여 각 인덱스 값에 걸맞는 최솟값을 넣어준다.

2와 3으로 나누어지지 않으면 무조건 -1을 빼줘야하기 때문에 먼저 a[i-1]부터 구한다.

1을 더하는 이유는 a[i]를 최소로 만들기 위해선 a[i-1]+1번이라는 공식이 만들어지기 때문이다.

이렇게 만들어진 a[i]를 각각 a[i/2], a[i/3]과 비교하여 더 작은 값을 저장한다.