[백준] 1463번 1로 만들기 파이썬 코드

코드

# 시간제한이 0.15초이고 각각의 경우 있을 수 있는 케이스를 모두 살펴보아야 한다.
# dp가 적격
# Tabulation 방식

def findcnt(n):
  dp = [0]*(n+1) # 개수를 세어주기 위한 dp 테이블을 만든다
  for i in range(2, n+1): # 아래에서부터 구한다.
    if i%6 == 0: dp[i] = min(dp[i//3], dp[i//2])+1
    # 6의 배수인 경우, dp[i//3], dp[i//2] 중 작은 값을 찾아 1을 더해준다.
    # 이 경우에서 dp[i-1]인 경우가 제외된 이유는 2의 배수, 3의 배수보다 값이 크기 때문이다.
    
    elif i%2 == 0: dp[i] = min(dp[i//2], dp[i-1])+1
    # 2의 배수인 경우, dp[i//2], dp[i-1] 중 작은 값을 찾아 1을 더해준다
    
    elif i%3 == 0: dp[i] = min(dp[i//3], dp[i-1])+1
    # 3의 배수인 경우, dp[i//3], dp[i-1] 중 작은 값을 찾아 1을 더해준다.
    
    else: dp[i] = dp[i-1]+1
    # 나머지 경우, 1을 더한 값에서 1을 더해준다
    
  return dp[n]
print(findcnt(int(input())))

dp와 친해지기 중...