BOJ-1633 - Python

30 ~ 1000개의 두 정수를 입력받는다. 중복되지 않으며 한 줄에 한 개의 수만 선택가능할 때, 앞 수 15개, 뒷 수 15개를 합친 최대 값을 출력하는 문제. 첫 풀이는 함수를 재귀적으로 활용하여 dp[정수의 길이][16][16]의 크기를 갖는 배열에 값을 할당, 비교하여 풀었으나 문제의 풀이가 길어져 두 번째 풀이는 3중 반복문을 이용하여 할당, 비교하여 풀었다. 다이내믹 프로그래밍 문제를 더 공부해야겠다.

# def dfs(white, black, current_index, length):
#
#     if white == 0 and black == 0:
#         return 0
#     if current_index == length:
#         return 0
#     if dp[current_index][white][black] != 0:
#         return dp[current_index][white][black]
#
#     dp[current_index][white][black] = dfs(white, black, current_index+1, length)
#     if white > 0:
#         dp[current_index][white][black] = max(dp[current_index][white][black], dfs(white-1, black, current_index+1, length) + wl[current_index])
#     if black > 0:
#         dp[current_index][white][black] = max(dp[current_index][white][black], dfs(white, black-1, current_index+1, length) + bl[current_index])
#     return dp[current_index][white][black]
#
# wl, bl = [], []
# length = 0
# total = 0
#
# while True:
#     try:
#         w, b = map(int, input().split())
#         length += 1
#     except:
#         break
#     wl.append(w)
#     bl.append(b)
#
# dp = [[[0] * 16 for _ in range(16)] for _ in range(length+1)]
# print(dfs(15, 15, 0, length))


wl, bl = [0], [0]
length = 0
while True:
    try:
        white, black = map(int, input().split())
        length += 1
    except:
        break
    wl.append(white)
    bl.append(black)

dp = [[[0] * 16 for _ in range(16)] for _ in range(length+1)]
for idx in range(1, length+1):
    for w in range(16):
        for b in range(16):
            dp[idx][w][b] = dp[idx-1][w][b]
            if w > 0:
                dp[idx][w][b] = max(dp[idx][w][b], dp[idx-1][w-1][b] + wl[idx])
            if b > 0:
                dp[idx][w][b] = max(dp[idx][w][b], dp[idx-1][w][b-1] + bl[idx])

print(dp[-1][-1][-1])

Written by@hyesungoh
Learning every moment

InstagramGitHubLinkedIn