[백준/파이썬] 1463번: 1로 만들기 풀이

🔗 문제 링크

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

1463번: 1로 만들기

  DP의 가장 기초적인 문제 중 하나이다. 어찌저찌 풀긴 했으나, 확실하게 짚고 넘어가기 위해 다양한 코드들을 살펴보고 이것들을 정리해 보도록 하겠다.

 

---

🔎 문제 풀이 & 작성 코드

  주어진 수를 3으로 나누거나, 2로 나누거나, 1로 빼는 연산을 반복하면서 1로 만들 수 있는 최소한의 연산의 횟수를 구하면 된다. 가장 적은 횟수로 만들려면 무작정 3으로 나눠보고, 안 나눠지면 2로 나눠보고, 그것조차 안될 때는 1로 빼는 식으로 계산하면 문제를 해결할 수 없다. 문제에서도 주어진 예시인데 10에 대해 생각해 보면 다음과 같다.

 

10 → 5 → 4 → 2 → 1 ; 우선 3으로 나누어보고, 나누어지지 않으면 2로 나누어보고, 그것도 안되면 1을 빼는 연산을 반복해 보았다. 총 4번의 횟수로 1을 만들 수 있다.
10 → 9 → 3 → 1 ; 하지만 실제 최소의 경우는 이와 같다. 10에서 1을 빼 9로 만든 다음 3으로 두 번 나누어지면 3번 만에 1로 만들 수 있다.

 

  이런 경우가 존재하기 때문에, 이 문제는 가능한 모든 경우의 수를 구해봐야 최솟값을 정확하게 찾을 수 있다. 하지만, 이 문제는 브루트 포스(모든 경우의 수를 반드시 일일이 구하는 방식)와는 다르다. 왜냐면 위에서 살펴본 10의 경우에, 9에서 1 로가는 최소 횟수에서 한 번만 더 연산을 진행하면 10의 최소 횟수를 구할 수 있기 때문이다. 시도할 수 있는 경우의 수를 모두 시도하되, 이전에 시도한 경우는 다시 시도하지 않고 활용하는 것이 다이내믹 프로그래밍, 즉 DP이다.

 

 

  DP의 가장 대표적인 풀이 방식이 Top-down과 Bottom-up이 있다. 두 방식으로 구할 수 있는 풀이를 모두 확인하겠다.

 

1. Top-Down(하향식) - 재귀 사용

  아직 DP에 익숙하지 않은 채로 구현한 코드라 다소 난잡하다 ㅠㅠ 블로그에 올리기 부끄럽지만,,, 그래도 공부하는 의미에서 용기 내서 올려본다..!! 재귀 방식을 사용하여 해당 숫자를 3으로 나눌 수 있을 때, 2로 나눌 수 있을 때, 1을 빼야 할 때를 각각 실행하면서 실행 횟수를 cnt라는 변수에 담아 계산하였다. 여러 경우를 각각 실행해 보면서 최소한의 횟수를 구했다. 약간 dfs의 개념과 짬뽕된 느낌이 강하지만..!! 그냥 가볍게 읽고 넘어가주었으면 한다 (;＾◇＾;) ゝ

N = int(input())

count = 100000

def dp(n, cnt):
    global count
    if cnt > count:
        return
    if n == 1:
        if cnt < count:
            count = cnt
        return
    if n % 3 == 0:
        cnt+=1
        dp(n//3, cnt)
        cnt-=1
    if n % 2 == 0:
        cnt+=1
        dp(n//2, cnt)
        cnt-=1
    cnt+=1
    dp(n-1, cnt)
    return

dp(N,0)
print(count)

 

  좀 더 깔끔한 방식의 Top-Down 풀이는 아래와 같다. 계산 결과를 딕셔너리에 저장하면서, 딕셔너리에 이미 저장된 값이 있으면 그 값을 호출하면서 사용한다는 특징이 있다. 두 번째 if~else 문을 살펴보게 되면, 주어진 숫자가 2와 3으로 모두 나뉠 수 있으면 두 가지 경우의 수를 비교해서 최소 횟수를 구하고, 2와 3중 하나로만 나누어진다면 해당 숫자로 나누는 경우와 1을 빼는 경우의 횟수를 비교한다. 마지막으로는 단순히 1을 빼주고 연산을 이어간다.

N = int(input())

num={1:0}

def dp(n):
    if n in num.keys():
        return num[n]
    if (n%3==0) and (n%2==0):
        num[n]=min(dp(n//3)+1, dp(n//2)+1)
    elif n%3==0:
        num[n]=min(dp(n//3)+1, dp(n-1)+1)
    elif n%2==0:
        num[n]=min(dp(n//2)+1, dp(n-1)+1)
    else:
        num[n]=dp(n-1)+1
    return num[n]

print(dp(N))

 

2. Bottom-up(상향식) - 반복문 사용

  상향식은 가장 간단하게 말하면 반복문을 사용하는 방식이다. 상향식이라는 이름처럼, 가장 작은 경우의 수부터 구해서 차근차근 가장 큰 수까지 계산해 나가는 방식이다. 아래 코드에서는 2부터 N까지의 계산을 실행하면서 최소 횟수를 구했다. for문의 앞에서 +1을 해주는 이유는, 1을 뺀 경우의 수를 나타내기 위함이다. 그다음 2와 3으로 나누어 떨어지는지 확인해 보며 최소 횟수를 다시 구해 리스트에 대입해 주며 정답에 접근한다.

N = int(input())

dp = [0] * (N+1)

for i in range(2, N+1):
    dp[i] = dp[i-1] + 1

    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)

print(dp[N])

 

 

---

🌍 깃허브 링크

실제 작성한 해당 정답 코드는 깃허브에도 업로드해두었습니다.

dohyun-99 - Overview