8-2. DP(다이나믹동적계획법) 문제2

정답 코드

#정수 N,M을 입력 받기
n,m = map(int, input().split())
#N개의 화페 단위 정보를 입력받기
array = []
for i in range(n):
    array.append(int(input()))

#한번 계산된 결과를 저장하기 위한 DP테이블 초기화
d = [10001] * (m+1)

#다이나믹 프로그래밍 진행(바텀업)
d[0] = 0
for i in range(n):
    for j in range(array[i], m+1):
        if d[j - array[i]] != 10001: #(i-k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j],d[j-array[i]]+1)

#계산된 결과 출력
if d[m] == 10001: #최종적으로 M원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

금광 문제

정답 코드

#테스트 케이스 입력
t = int(input())

for _ in range(t):
    #금광 정보 입력
    n, m = map(int, input().split())
    array = list(map(int,input().split()))
    #다이나믹 프로그래밍을 위한 2차원 DP테이블 초기화
    dp = []
    index = 0
    result = 0
    for i in range(n):
        dp.append(array[index:index+m])
        index += m
    #다이나믹 프로그래밍 진행
    for j in range(1,m): #열
        for i in range(n): #행
            # 왼쪽 위에서 오는 경우
            if i == 0: left_up =0
            else:left_up = dp[i-1][j-1]
            #왼쪽 아래에서 오는 경우
            if i == n - 1: left_down = 0
            else:left_down = dp[i+1][j-1]
            # 왼쪽에서 오는 경우
            left = dp[i][j-1]
            #2번째 열부터 전 열에서 온 값 + 왼쪽위,왼쪽아래,왼쪽 중 가장 큰값을 더한다.
            dp[i][j] = dp[i][j] + max(left_up,left_down,left)

    for i in range(n):
        result = max(result,dp[i][m-1])
    print(result)

문제3 병사 배치하기

나의 코드

n = int(input())
array = list(map(int,input().split()))

result = 0
for i in range(n):
    if i != n-1:
        if(array[i] < array[i+1]):
            result += 1
print(result)

정답 코드

n = int(input())

array = list(map(int,input().split()))
#순서를 뒤집어 '최장 증가 부분 수열' 문제로 전환
#array.reverse() #밑에서 부호를 if array[j] > array[i]: 로 설정해도 가능

#DP를 위한 1차원 DP테이블 초기화
dp = [1] * n

#가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
for i in range(1,n):
    for j in range(0,i):
        if array[j] > array[i]:
            dp[i] = max(dp[i],dp[j]+1) #dp[i] = dp[j+1] 도가능
print(dp)
#열외해야 하는 병사의 최소 수를 출력
print(n-max(dp))