[BEAKJOON] 백준 1463번 : 1로 만들기

 

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

1463번: 1로 만들기

 

 

문제 설명

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

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

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

 

 

 

DP- BottomUp (for 문 사용)

문제 해결 방법

 

처음에 dp라는 리스트를 num+1만큼의 크기만큼 0으로 초기화해준다.

dp[1]=0, 그러면 dp[1]은, 값이 1일 경우, 1이 되는 경우의 수는 0이라는 의미를 가진다.

dp[2]=1, 그러면 dp[2]인 값은, 1이 되기 위해서 -1이라는 연산을 한번해주어야 하기 때문에 아래와 같은 코드가 필요하다.

dp[i] = dp[i-1]+1

그렇게 되면, if(i%2==0)의 if 분기문에 걸리게 되는데,

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

그러면 dp[2], dp[1]+1의 값은 동일하기 때문에 값에 변화는 없다.

 

dp[3]의 값은 이전에 값을 더해줘서 3이되는데,

dp[3], dp[1]+1은 2, 1이기 때문에 더 적은 값인 1이 된다.

즉, 3에서 3을 나누면 한번의 연산으로 1이 나오는 것이다.

 

for i in range(2, num+1):

2부터 num까지 i를 사용해서 반복

 

dp[i] = dp[i-1]+1

dp[i]는 숫자 i가 1이 되는데 까지 걸리는 최소한의 연산 횟수를 저장해야 한다.

i에서 1을 빼면 i-1이 되므로, d[i-1] + 1을 함으로써, d[i-1] (i-1이 1이 되는데의 최소한의 연산 횟수) + 1 (i에서 1을 빼서 i-1이 되는데 필요한 연산 횟수 1회)로 초기화를 합니다.

 

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

i가 2로 나누어떨어질 때, d[i//2]+1, d[i] 중에서 최솟값을 d[i]에 저장한다.

d[i]는 위에서 초기화한 d[i-1]+1의 값이 들어가 있다. 이것과 d[i//2]+1를 비교하여 최솟값을 d[i]에 넣는다.

d[i//2]는 i가 2로 나누어 떨어진다고 조건문에서 확인했으니, i를 2로 나눈 값이 1이 되는데 걸리는 최소한의 연산 횟수를 의미한다.

즉, d[i//2]+1 는 i를 2로 나눈 값이 1이 되는데 걸리는 최소 연산 횟수 +i를 2로 나누는 연산횟수 1회이다.

 

3로 마찬가지다.