BOJ 1463 1로 만들기

LONGNEW·2021년 1월 13일
0

BOJ

목록 보기
30/333

https://www.acmicpc.net/problem/1463
시간 0.5초, 메모리 128MB
input :

  • N (1 <= N <= 10^6)

output :

  • 연산을 하는 횟수의 최솟값을 출력.

조건 :

  • 정수에 사용하는 연산.
  1. X가 3으로 나누어 떨어지면, 3으로 나눔.
  2. X가 2로 나누어 떨어지면, 2로 나눔.
  3. 1을 뺌.

DP 없이 재귀만 써서 하면 시간 초과가 발생할까?

최대 입력 되는 숫자는 1,000,000 1로 빼기만 해도 1백만 밖에 안 걸림..

재귀 함수로 구현하려 했는데.. 3 경우 모두 계산 해 줘야 하는데도 리턴에 걸려서 함수 밖으로 나가는 경우 발생.

dp 리스트 전체를 다 계산 해 놓고 인덱스로 아이템을 가져오자.

정답 코드 :

import sys

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

for i in range(1, n + 1):
    if i == 1:
        dp[1] = 0
        continue
    dp[i] = dp[i - 1] + 1
    if i % 3 == 0 :
        dp[i] = min(dp[i], dp[i // 3] + 1)
    if i % 2 == 0 :
        dp[i] = min(dp[i], dp[i // 2] + 1)

print(dp[n])


점화식 만들기 부터 하고.
리스트를 다 채울지. 필요한 부분만 위에서 부터 재귀로 부를지. 생각해보자

0개의 댓글