Baekjoon 1463 | 1로 만들기 (Python)

📌문제

SILVER3 / 다이나믹 프로그래밍 (dp)

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

📌문제 분석 및 설계

문제보고 그냥 바로 while 쓰다가 갑자기 어..? 이거 dp문제인거같은데...? 싶어서

초기화하면서 식을 찾아나갔다.

 

쓰다보니 해당 수의 dp[하나작은수]+1과 3으로 나뉘면 dp[ 3으로 나눈 몫]+1과 비교해 최솟값으로 ,

아님 2로 나뉘면 dp[2으로 나눈 몫]값과 비교해 최솟값으로 ,

만약 3과 2로 둘다 나뉘어진다면  dp[하나작은수]+1 과 dp[ 3으로 나눈 몫]+1, 그리고 dp[2으로 나눈 몫]과 비교해 최솟값으로 지정!!!

 

나능 사실 마지막 3과2로 둘다 나뉘어질때를 고려를 안해서 틀리다 발견했다. 이러니 설계부터 완전히 하고 코딩하는게 좋다.

그리고 BFS도 된다는데 아직 구상해보진 못했다.

(처음으로 문제유형보지않고 dp문제인걸 알고, 처음으로 DP문자 혼자 풀어봐서 너무 뿌_듯)

 

📌소스 코드

n=int(input())
dp=[0]*(1000001)
dp[2]=1
dp[3]=1
dp[4]=2
dp[5]=3

for i in range(6,n+1):
    if i%3==0 and i%2!=0:
        dp[i]=min(dp[i-1]+1,dp[i//3]+1)
    elif i%3 !=0 and i%2==0:
        dp[i]=min(dp[i-1]+1,dp[i//2]+1)
    elif i%3==0 and i%2==0:
        dp[i]=min(dp[i-1]+1,dp[i//2]+1,dp[i//3]+1)
    else:
        dp[i]=dp[i-1]+1
print(dp[n])