1463. 1로 만들기

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

1463번: 1로 만들기

d[n] : n 이라는 숫자를 주어진 연산으로 1로 만들 수 있는 연산의 최소 횟수.

 

주어진 연산:

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

그렇다면

d[n-1]은 n-1이라는 숫자를 주어진 연산으로 1로 만들 수 있는 연산의 최소 횟수이다. 

n - 1에서 1을 더하는 연산(3번째 연산)이 1회 수행되면 n이기 떄문에

d[n] = d[n - 1] + 1

 

같은 방식으로

d[n / 2]는 n / 2 라는 숫자를 주어진 연산으로 1로 만들 수 있는 연산의 최소 횟수이다. 

n에서 2를 나누는 연산(2번째 연산)이 1회 수행되면 n / 2이기 때문에

d[n] = d[n/2] + 1

 

d[n/3]는 n / 3 라는 숫자를 주어진 연산으로 1로 만들 수 있는 연산의 최소 횟수이다. 

n에서 3을 나누는 연산(1번째 연산)이 1회 수행되면 n / 3이기 떄문에

d[n] = d[n / 3] + 1

 

즉 d[n]은 

d[n] = d[n - 1] + 1

d[n] = d[n/2] + 1

d[n] = d[n / 3] + 1

 

세가지 방법으로 구할수 있기때문에 이 세가지 중 가장 작은 값이 우리가 구하는 답이다.

 

d = [0] * 1000001
d[1] = 0

n = int(input())

for i in range(2, n+1):
    v = d[i - 1] + 1
    if i % 2 == 0: v = min(d[i//2] + 1, v)
    if i % 3 == 0: v = min(d[i//3] + 1, v)

print(d[n])

 

 

// 추가

배열의 값에 해당 idx가 1이 되려면 해야 하는 최소한의 연산 횟수가 기록된다.

d[2]에는 2가 1이 되기 위해 수행된 최소한의 연산 횟수가 기록되어 있을것이다. 그 값은 1이다. (d[2] = 1)

 

그렇다면 d[4]는? 

d[4/2] = d[2]에서 한번의 연산 (곱하기 2)만 수행하면 되므로 d[2]+1

d[4-1] = d[3]에서 한번의 연산 (더하기 1)만 수행하면 되므로 d[3]+1

4/3은 불가능.

따라서 d[2]+1, d[3]+1 중 작은 값이 d[4]가 된다.

 

...