1463

날짜 : 2022. 10. 21

사용 언어 : python

 

문제

 

 

코드

Bottom-Up 방식 : 속도가 훨씬 빠르다(참고한 답안)

import sys

n = int(sys.stdin.readline())
d = [0] * (n+1)

for i in range(2, n+1):# 역순으로 진행 (1부터 n까지)
    d[i] = d[i-1] + 1 # 1을 더한 경우
    if i % 3 == 0:
        d[i] = min(d[i], d[i//3] + 1) # 1을 뺐을 때와 나누었을 때의 횟수 비교
    if i % 2 == 0:
        d[i] = min(d[i], d[i//2] + 1)

print(d[n])

 

Top-Down 방식 : 속도가 느리지만 직관적으로 풀었다.(참고 x)

import sys
sys.setrecursionlimit(10**6)
n = int(sys.stdin.readline())
dp = [10e9] * (n + 1)  # 방문체크


def check(num):  # 숫자, 연산횟수
    # print(num)
    if num == 1:
        return
    if num % 3 == 0 and dp[num // 3] > dp[num] + 1:  # 나누어 떨어지고 갱신 가능한 경우
        dp[num//3] = dp[num] + 1
        check(num // 3)
    if num % 2 == 0 and dp[num // 2] > dp[num] + 1:
        dp[num//2] = dp[num] + 1
        check(num // 2)
    if dp[num - 1] > dp[num] + 1:
        dp[num-1] = dp[num] + 1
        check(num - 1)
    return
dp[n] = 0
check(n)
print(dp[1])

 

알게된 점

- 첫 다이나믹 프로그래밍 문제였다.

- 첫 보기엔 그리디같아서 n에서 1까지 3으로 나누고 (n-1) % 3 이 0일때 1을 차감하고 나머지는 2로 나누는 식으로 했지만 계속 틀렸다.

- 그래서 100, 200 등 다양한 수를 넣었지만 너무 많은 경우의 수가 나와 결국 DP의 개념과 다른 사람들의 문제를 참고했다.

- 대략적인 풀이는 1부터 n까지 역순으로 진행하고, 각 수마다 진행되는 연산의 수를 비교하면서 풀이하는 것이었다.

- 원리는 간단해 보이는데 그리디만 풀어서 그런지 빠르게 익숙해져야겠다는 생각이 든다.

 

 

* 두 번째 풀이

- 10에서 3으로 나누었을 때, 2로 나누었을 때, 1을 차감했을 때의 케이스를 저장하는 리스트를 만들고, 갱신이 가능한 경우 재귀하는 방식으로 문제를 전개했다.

- 맨 처음 if~ elif~로 풀어서 정답이 확실히 나오지 않았지만 수정 후 개선되었다.

- 지난번에는 풀이를 참고했지만 이번에는 직접 풀어서 나름 뿌듯하다.

 

참고 사이트

- https://jae04099.tistory.com/199

[파이썬] 백준 - 1463: 1로 만들기 (매우 자세한 해설 포함)