1 분 소요

백준 1463번 1로 만들기 문제 풀이를 해보겠습니다.

출처 : 백준

문제

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

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

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

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

풀이

문제 설명: 메모이제이션으로 N을 1로 바꾸기 위해 주어진 연산을 몇 번 사용하는지 계산하는 문제

문제 설명에서는 메모이제이션을 사용하라고 했지만 나는 간단하게 문제를 풀기위해 Bottom-Up 방식을 사용했다. 1 ~ N 까지 연산 횟수를 저장할 리스트(dp)를 생성하고 그 리스트를 이용해 dp[N]을 구해 출력할 것이다.

연산 규칙을 통해 점화식을 만들어 본다면 아래와 같다

  • dp[10] = (dp[10-1] + 1) or (dp[10//2] + 1)
  • dp[5] = dp[5-1] + 1
  • dp[4] = (dp[4-1] + 1) or (dp[4//2] + 1)
  • dp[2] = dp[2-1] + 1

즉,

  • dp[i] = dp[i-1] + 1
  • dp[i] = dp[i//3] + 1
  • dp[i] = dp[i//2] + 1

가장 적은 연산 횟수를 구해야 하기 때문에 1을 빼는 것을 기본규칙으로 계산하고

2나 3으로 나눌 수 있으면 나눈 후, 둘을 비교해 더 작은 값을 저장할 것이다.

코드

import sys
input = sys.stdin.readline

def main():
    N = int(input().strip()) 

    dp = [0] * (N + 1) #연산횟수를 저장할 리스트 생성

    for i in range(2, N + 1): # N이 1이면 0이기 때문에 2부터 N까지 계산
        # 기본 규칙 : 1을 뺀다
        dp[i] = dp[i - 1] + 1 # 연산을 수행했으니 1을 더한다
        
        # 2로 나눴을때 나머지가 없으면 2로 나눈다
        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i // 2] + 1) 
        # 연산 횟수가 더 적은걸 dp[i]에 저장한다.

        # 3으로 나눴을때 나며지가 없으면 3으로 나눈다
        if i % 3 == 0:
            dp[i] = min(dp[i], dp[i // 3] + 1)
        # 연산 횟수가 더 적은걸 dp[i]에 저장한다.
    print(dp[N])

main()

댓글남기기

참고