BOJ(1로만들기)

작성일 | In

DP 기본적인 설명

  • 1로 만들기

  • DP의 대표 문제
  • 아래 2가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다.
    1. Overlapping Subproblem - (문제를 작은 문제로 쪼갤 수 있다.)
    1. Optimal Substructure - (문제의 정답을 작은 문제의 정답에서 구할 수 있다)

  • Optimal Substrucutre를 만족하면, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다

  • 다이나믹 프로그래밍에서는 각 문제는 한번만 풀어야 한다
  • Optimal Substrucutre를 만족하기 때문에 같은 문제는 구할 때마다 정답이 같다.

  • 따라서 정답을 한번 구했으면, 어딘가에 메모해놓아야 하며, 이를 Memoization이라고 한다

  • 다이나믹 프로그래밍을 푸는 방법은 크게 두가지이다.
    1. Top-down : 문제를 작은 문제로 나눈다 - 작은 문제를 푼다 -> 작은 문제를 풀었으니 이제 문제를 푼다
      • 재귀 호출을 이용해서 문제를 쉽게 풀 수 있다.
    1. Bottom-up : 문제를 크기가 작은 문제부터 차례대로 푼다 -> 문제를 조금씩 크게 만들면서 문제를 푼다 -> 작은 문제를 풀면서 왔기에, 큰 문제는 항상 풀 수 있다 -> 언젠가 풀어야 하는 문제를 풀 수 있다.

1로 만들기 1463

  • 정수 X에 사용할 수 있는 연산은 다음과 같이 세가지다
  • X가 3으로 나누어 떨어지면 3으로 나눈다
  • X가 2로 나누어 떨어지면, 2로 나눈다

  • 1을 뺀다

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

Bottom up으로 풀어보기

N = int(input())
d = [0]*(N+1)
d[1] = 0
for i in range(2, N+1):
    d[i] = d[i-1]+1
    if i % 2 == 0 and d[i] > d[i//2]+1:
        d[i] = d[i//2]+1
    if i % 3 == 0 and d[i] > d[i//3]+1:
        d[i] = d[i//3]+1
print(d[N])

N = int(input())
d = [0]*(N+1)
d[1] = 0
for i in range(2, N+1):
    d[i] = d[i-1]+1
    if i % 2 == 0:
        d[i] = min(d[i], d[i//2]+1)
    if i % 3 == 0:
        d[i] = min(d[i], d[i//3]+1)
print(d[N])

Top down (재귀)로 풀어보기

import sys
sys.setrecursionlimit(10000000)


def go(n):
    if n == 1:
        return 0
    if d[n] > 0:
        return d[n]
    d[n] = go(n-1)+1
    if n % 2 == 0:
        temp = go(n//2)+1
        if d[n] > temp:
            d[n] = temp
    if n % 3 == 0:
        temp = go(n//3)+1
        if d[n] > temp:
            d[n] = temp
    return d[n]


N = int(input())
d = [0]*(N+1)
print(go(N))
  • 백준 문제를 통과하지 않는다.
  • pypy로 하면 시간초과
  • python3으로 하면 메모리 초과가 나온다.
  • 어떻게 재귀로 통과시켜줄 수 있는지 모르겠다.

참고자료 codeplus

0%