[백준/Python] 1463 1로 만들기

[백준/Python] 1463 1로 만들기

정답 코드 및 설명

전체 코드

def min_operations(n):
    dp = [0] * (n + 1)  # dp 배열 초기화
    
    for i in range(2, n + 1):
        # 기본 연산: 1 빼기
        dp[i] = dp[i - 1] + 1
        
        # 2로 나누기 가능 시 최솟값 갱신
        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i // 2] + 1)
        
        # 3으로 나누기 가능 시 최솟값 갱신
        if i % 3 == 0:
            dp[i] = min(dp[i], dp[i // 3] + 1)
            
    return dp[n]

print(min_operations(int(input()))) 

각 정수에 대하여 1로 만드는 데 필요한 최소 연산 횟수를 저장하는 방식으로 문제를 푼다.

1. 정수 N 을 1로 만들기 위한 최소 연산 횟수를 저장할 배열 dp 를 생성하고 dp[i] 는 정수 i를 1로 만들기 위한 최소 연산 횟수이다.

2. dp[1] 은 0으로 초기화 한다

3. 모든 정수 i 에 대해서 다음 3가지 연산 중 하나를 적용할 수 있다.

   • 만약 i 가 3으로 나누어 떨어진다면, dp[i/3] + 1 을 계산한다
   • 만약 i 가 2으로 나누어 떨어진다면, dp[i/2]+ 1 을 계산한다
   • dp[i-1] + 1 을 계산한다

4. 위 3 가지 연산으로 계산된 값 중 최소값을 dp[i] 에 저장한다