[Gold III] 원숭이 키우기 - 1423
성능 요약
메모리: 121364 KB, 시간: 528 ms
분류
다이나믹 프로그래밍
문제 설명
준규는 심심해서 4592스토리라는 게임을 만들었다. 4592스토리에서는 한 플레이어가 여러 개의 캐릭터를 동시에 조정해야 한다. 이 게임은 동시 접속자가 1억명 정도 나오는 매우 성공한 게임이다.
해빈이는 가지고 있는 캐릭터를 D일동안 훈련시키려고 한다. 캐릭터의 레벨은 1보다 크거나 같고, N보다 작거나 같은 정수이다.
해빈이는 하루에 한 캐릭터를 고를 수 있다. 캐릭터를 하루동안 훈련시키면, 그 캐릭터의 레벨이 1 오른다. 예를 들어, 레벨이 1인 캐릭터를 훈련시키면 2가 되고, 레벨이 2인 캐릭터를 훈련시키면 3이 된다. 레벨이 N인 캐릭터는 훈련을 시켜도 레벨이 오르지 않는다. 같은 캐릭터를 연속해서 훈련을 시켜도 된다. 어떤 캐릭터를 3일 연속으로 훈련시키면, 그 캐릭터의 레벨은 3이 오르게 된다. 꼭 캐릭터를 고를 필요는 없다. 하루는 게임을 하지 않고 그냥 쉬어도 된다.
해빈이가 가지고 있는 캐릭터의 수가 각 레벨 별로 주어진다. 이때, 적절히 훈련을 시켜서 캐릭터의 힘의 합을 최대로 만드는 프로그램을 작성하시오.
예를 들어, 레벨이 5까지 있고, 레벨이 1, 2, 3, 4, 5인 캐릭터를 각각 1, 2, 3, 4, 5마리 가지고 있는 경우를 생각해보자. 또, 레벨이 1, 2, 3, 4, 5인 캐릭터의 힘이 각각 1, 2, 3, 4, 5인 경우이다. 가장 처음에 해빈이가 가지고 있는 캐릭터의 힘의 합은 1*1 + 2*2 + 3*3 + 4*4 + 5*5 = 55가 된다. 10일동안 적절히 훈련시키면 힘의 합 65를 만들 수 있다.
해빈이가 가지고 있는 캐릭터의 수가 각 레벨별로 주어지고, 각 레벨에 해당하는 힘이 주어졌을 때, D일동안 훈련시켜서 얻을 수 있는 캐릭터의 힘의 합 중 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 캐릭터의 최대 레벨 N(1 ≤ N ≤ 50)이 주어진다. 둘째 줄에는 해빈이가 가지고 있는 캐릭터의 수가 각 레벨 별로 주어진다. 셋째 줄에는 캐릭터의 힘이 각 레벨 별로 주어진다. 각 레벨 별 캐릭터의 수와 힘은 1,000,000보다 작거나 같은 음이 아닌 정수이다. 넷째 줄에는 훈련시킬 수 있는 기간인 D (1 ≤ D ≤ 100)가 주어진다.
출력
첫째 줄에 D일동안 훈련시켜서 얻을 수 있는 캐릭터의 힘의 합 중 최댓값을 출력한다.
풀이
이런 문제는 완전탐색에 기반하여 생각해야한다.
고려해야할 변수가 3개이므로 3차원 dp를 생각했다.
동전 분할이랑 비슷한 느낌임.
고민 많이 한 부분은 어떻게 변화한 배열을 유지시킬까이다. 배열을 모두 불러올수는 없기에, 인덱스를 이용하던 경험을 되살려 앞에서부터 쓸어오듯 인덱스를 넘기는 방식이다.
즉, 인덱스번호에 있는 캐릭터를 옮기느냐 옮기지 않느냐 둘로 구분한다.
두번째는 기저사례이다.
1. 인덱스에 있는 캐릭터가 없다면 리턴
2. 모든 진행횟수가 지났다면 리턴
3. 인덱스의 끝에 도달했다면 리턴
마지막은 dp 값이다.
dp[index][process] = max_val
고려할 요소가 너무 많아 복잡해졌다.
mx_level = int(input())
character = list(map(int, input().split()))
power = list(map(int, input().split()))
trn = int(input())
dp = [[-1]*mx_level for _ in range(trn)]
def solve(index, process, is_lvup):
print(dp)
print(index, process, is_lvup)
tmp = character[index]
if is_lvup:
tmp += 1
if index == mx_level-1 or process == trn: # 마지막 인덱스에 도달했거나 시간이 다 된 경우
print("a", tmp * power[index])
return tmp * power[index]
if dp[index][process] != -1: # dp에 값이 있는 경우
print("b")
return dp[index][process]
if character[index] == 0: # 현재 레벨에 캐릭터가 없는 경우
print("c")
return solve(index+1, process, False)
calc = tmp * power[index]
dp[index][process] = max(solve(index + 1, process, False),
solve(index + 1, process+1, True)) + calc
return dp[index][process]
solve(0, 0, False)
solve(0, 1, True)
print(dp)내 코드인데 일단 문제점은 설계가 잘못되었다.
이전값을 기준으로 현재값을 1개 늘리는것은 반영되었는데 이전값을 줄이는게 반영이 안되었다.
거기서 멘붕이 와서 답을 참고한다.
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
MAX = 51
def get_dp(idx1, idx2, idx3):
if idx2 == n - 1:
return 0
if dp[idx1][idx2][idx3] != -1:
return dp[idx1][idx2][idx3]
ret = 0
for i in range(idx3 + arr[idx2] + 1):
if idx1 >= i:
ret = max(ret, get_dp(idx1 - i, idx2 + 1, i) + (power[idx2 + 1] - power[idx2]) * i)
dp[idx1][idx2][idx3] = ret
return ret
def max_character_power(n, arr, power, d):
result = sum(arr[i] * power[i] for i in range(n))
return result + get_dp(d, 0, 0)
n = int(input())
arr = list(map(int, input().split()))
power = list(map(int, input().split()))
d = int(input())
dp = [[[-1] * 105 for _ in range(MAX)] for _ in range(105)]
print(max_character_power(n, arr, power, d))
아이디어
코드
MAX_N = 51
def get_dp(idx1, idx2, idx3):
if idx2 == n - 1:
return 0
if dp[idx1][idx2][idx3] != -1:
return dp[idx1][idx2][idx3]
ret = 0
for i in range(idx3 + arr[idx2] + 1):
if idx1 < i:
break
ret = max(ret, get_dp(idx1 - i, idx2 + 1, i) + (power[idx2 + 1] - power[idx2]) * i)
dp[idx1][idx2][idx3] = ret
return ret
n = int(input())
arr = list(map(int, input().split()))
power = list(map(int, input().split()))
d = int(input())
result = sum(arr[i] * power[i] for i in range(n))
dp = [[[-1] * 105 for _ in range(MAX_N)] for _ in range(105)]
print(result + get_dp(d, 0, 0))
탑다운으로 풀었었는데 메모리초과랑 시간초과의 향연으로 바텀업 방식이다.
너무 어려웠음. 냅색문제처럼보이긴 햇는데 아닌것 같기도 하고, 점화식 세우는것도 너무 어려웠음.
회고
문제가 너무 어려웠다. 고려할 요소도 많았고 2차원일지 3차원일지 고민도 많았다. 다른 사람 푼걸 보니 1차원으로 풀었고 무슨 bounded knapsack (결국 냅색인가..) 로 풀었는데 이해가 하나도 안간다.
이 문제 다시 풀어봐야한다. 저거 내가 푼거 아니다..
