이것이 취업을 위한 코딩 테스트다 CHAPTER 8 다이나믹 프로그래밍

• 다이나믹 프로그래밍 사용 조건
  • 큰 문제를 작은 문제로 나눌 수 있다.
  • 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
• 메모이제이션
  • 다이나믹 프로그래밍을 구현하는 방법 중 하나
  • 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법
  • 메모이제이션은 값을 저장하는 방법으로 캐싱(Caching)이라고도 한다.
• 다이나믹 프로그래밍
  • 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법
  • 탑다운 방식
    • 큰 문제를 해결하기 위해 작은 문제를 호출
    • 재귀함수 활용
    • 하향식
  • 보텀업 방식
    • 단순히 반복문을 이용하여 작은 문제를 먼저 해결하고, 해결된 작은 문제를 모아 큰 문제를 해결하는 방식
    • 상향식

문제 2. 1로 만들기

'''

    Chapter 8. 1로 만들기

    접근법 1

        정수 X가 1이 될때까지 가능한 모든 경우 계산

        값을 계속 기억하고 있어야 하므로 메모이제이션 -> dp

'''

import sys
input = sys.stdin.readline

X =int(input())
dp = [float('inf')]*(X+1)
dp[X] = 0

for i in range(X,0,-1):
    # 정수 X가 5로 나누어떨어지면
    if i%5 == 0:
        dp[i//5] = min(dp[i//5], dp[i]+1)
    # 정수 X가 3로 나누어떨어지면
    if i%3 == 0:
        dp[i//3] = min(dp[i//3], dp[i]+1)
    # 정수 X가 2로 나누어떨어지면
    if i%2 == 0:
        dp[i//2] = min(dp[i//2], dp[i]+1)
    # 정수 X에서 1을 뺀다
    dp[i-1] = min(dp[i-1], dp[i]+1)

print(dp[1])

 

문제 3. 개미 전사

'''

    Chapter 8. 개미 전사

    접근법 1

        i번째 창고를 털면 i+2번째 창고 혹은 i+3번째 창고를 털 수 있다.

        (더 뒤 창고도 털 수 있지만 최대한 많이 털어야 하므로 둘 중 하나를 무조건 털고 넘어가야한다.)

            i+2번째와 i+3번째 중 더 큰 것을 털면 된다.

        0번째 창고를 터는 경우와 1번째 창고를 터는 경우 중 더 큰 경우가 답

            둘은 함께 할 수 없는 경우

'''

import sys
input = sys.stdin.readline

N = int(input())
store = list(map(int,input().split())) + [0]

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

print(max(store[:2]))

 

문제 4. 바닥 공사

'''

    Chapter 8. 바닥 공사

    접근법 1  

        A(1) = 1

        A(2) = 3

        A(3)는 (A(2)에서 2X1 한개 추가) + (A(1)에서 1x2 2개 추가, 2x2 1개 추가)

            즉, A(3) = A(2) + A(1)*2

        따라서, A(N) = A(N-1) + A(N-2)*2 (N > 2)

'''

import sys
input = sys.stdin.readline

N = int(input())
dp = [0]*(N+1)
dp[1],dp[2] = 1,3
for i in range(3,N+1):
    dp[i] = (dp[i-1] + dp[i-2]*2)%796796

print(dp[N])

 

문제 5. 효율적인 화폐 구성

'''

    Chapter 8. 효율적인 화폐 구성

    접근법 1

        적은 금액부터 큰 금액까지 확인하여 차례대로 만들 수 있는 최소한의 화폐 개수 찾기

'''

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
coin = []
for _ in range(N):
    c = int(input())
    if c <= M:
        coin.append(c)

dp = [float('inf')]*(M+1)
dp[0] = 0

for i in range(M):
    for j in coin:
        if i + j <= M:
            dp[i+j] = min(dp[i+j],dp[i]+1)

if dp[M] == float('inf'):
    print(-1)
else:
    print(dp[M])