반응형
개인적으로 굉장히 어려웠던 문제...
첫째로, 최대 수도관 용량으로 dp를 할지, 길이로 dp로 할지 정한다고 해맸다.
두번째로, 입력받아서 배열에서 꺼내쓰려다가 시간초과로 쳐맞았다.
세번째로, 중복사용때문에 고생했다.
아무튼 코드는 아래와 같다.
초기화 방법은 입력값이 1이라고 하면
dp[1]이 들어가는 모든 값의 합을 바꾼다. x가 7이라고 한다면,
dp[7]=min(1,dp[7-1])이다.
그리고 만약 dp[7]이 입력이 들어오면 변경 해주는 방식이다.
d, p = map(int, input().split())
dp = [0 for _ in range(d+ 1)]
for _ in range(p):
l, c = map(int, input().split())
for x in reversed(range(d+1)):
if x>=l:
dp[x] = max(dp[x], min(c, dp[x-l]))
if c > dp[l]:
dp[l] = c
print(dp[-1])여기서 reversed가 안들어가게 되면 바텀업이 되어 예제를 보면 (2,7)이 있는데 이게 두번쓰여서 7의 값이 6이된다.
5를 만드는데 2를 한번 쓰고, 7을 만드는데 2를 한번 더 썼기 때문이다.
제출은 pypy로 해야 된다.
반응형
