백준) 1463 - 1로 만들기 (Python)

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

1463번: 1로 만들기

생각

DP 문제의 기본이라고 부를 수 있는 문제이다. DP를 사용하지 않고 문제를 해결할 수도 있으나 DP를 제대로 배우고 써보고자 활용해서 문제를 해결하려 했다.

 

문제의 입력에 대한 출력 값을 보면서 왜 그러한 값들이 나왔는지 머릿속으로 계속해서 과정을 그려봤다.

 

내 코드

n=int(input())
d=[0]*(n+1)
d[0]=0
d[1]=1
d[2]=1
d[3]=1
for i in range(4,n+1):
    if i%3==0:
        d[i]=min(d[i//3]+1,d[i-1]+1)
    elif i%2==0:
        d[i]=min(d[i//2]+1,d[i-1]+1)
    else:
        d[i]=d[i-1]+1
print(d[n])

 

 

출력 값에 대해서 처음 1~3까지의 출력값은 정해두고 그 뒤부터 dp를 적용해봤다.

3으로 나누어지는 경우, 예를 들어서 n=9일 떄 n=3일때의 결과값에 3으로 나눈 횟수 1번만 더하면 n=9일때의 횟수를 구할 수 있기에 구현했다. 그 후 원래 1을 빼서 계산하는 결과와 횟수를 비교해서 최솟값을 dp 테이블에 넣는 방식으로 구현했다. 

2의 경우도 마찬가지의 로직을 적용했다.

그 외에는 1을 빼는 연산을 진행하므로 1을 빼는 연산에 대한 횟수 계산만 진행했다.

 

그러나 제출 결과 틀렸다는 결과가 나왔다.

아무래도 먼저 i가 3의 배수인지 2의 배수인지의 로직을 거치고 나서 그 후에 d[i]를 계산하는 방식에 있어서 문제가 발생하는 듯 하다.

풀이

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

풀이에는 먼저 d[i]를 계산해서 결과값을 저장시킨 후 i의 값에 따라 계산하는 방식으로 적용했다.

 

dp의 bottom-up 방식의 경우 일반적인 계산식을 먼저 적용시키고 그 후 문제에서 주어진 조건에 따라 계산식을 바꿔서 dp 테이블에 값을 넣어서 결과를 도출하는 구조라는 것을 이번 문제를 풀면서 알게 되었다.