[백준] 18353번 병사 배치하기

💡문제접근

• 다이나믹 프로그래밍을 이용하는 문제로 이중 for문으로 구현할 수 있었다.

💡코드(메모리 : 31120KB, 시간 : 784ms)

import sys
input = sys.stdin.readline

N = int(input())
lst = list(map(int, input().strip().split()))
dp = [1] * (N+1)

for i in range(1, N):
    for j in range(i):
        if lst[i] < lst[j]:
            dp[i] = max(dp[i], dp[j] + 1)
print(N - max(dp))

💡소요시간 : 19m

📌 Top-Down 방식이란?

• "재귀함수"로 다이나믹 프로그래밍 소스 코드를 작성하는 방식
• Top-Down 방식에는 "메모이제이션"이 활용된다.
• 메모이제이션이란 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다.

# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100
 
# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x):
    # 종료 조건(1 혹은 2일 때 1을 반환)
    if x == 1 or x == 2:
        return 1
    # 이미 계산한 적 있는 문제라면 그대로 반환
    if d[x] != 0:
        return d[x]
    # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]

print(fibo(99))

📌 Bottom-Up 방식이란?

• 단순히 "반복문"으로 다이나믹 프로그래밍 소스 코드를 작성하는 방식
• 작은 문제부터 차근차근 답을 도출
• Dp 테이블이 활용된다.

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])