포도주 시식 백준 파이썬 풀이

링크

문제 이해하기

문제를 보자마자 저번에 풀었던 그 계단 건너기 문제가 떠올랐다

하지만 계단문제와다르다  계단문제는 모든 숫자를 다 건너가야하고, 맨끝 계단을 반드시 밟아야했다

이문제는 최대값이 되게 숫자를 집으라는것뿐 모든 숫자를 집으라는 말은 없었다

뭐 어차피 최대값을 나오게 하려면 대부분의 경우 모든 숫자를 다 집어야겠지만 

그게 차이점이다

 

배열된 숫자들이 있고 거기서 고른 숫자가 최댓값이 되게 고른다

단. 연속으로 3숫자를 선택할수없다는 조건이 있다

 

입력

첫째줄에 포도주 잔의 개수 n이 주어짐 1 ≤ n ≤ 10,000

둘째줄부터 n+1줄까지 포도주잔안에 들어있는 포도주의 양이 순서대로 주어짐

포도주의 양은 음이 아닌 정수

 

출력

첫째줄에 최대로 마실수있는 포도주의 양을 출력

 

첫번째 아이디어

입력으로 6 10 13 9 8 1이

주어졌다고 생각해보자

 

동적계획법으로 접근한다

6부터 시작하여 숫자를 하나씩 추가하면서 주어진수에서 최대값을구한다

각 동적계획법 단계마다 연속된수일경우의 최대값 연속되지않은경우의 최대값을 따로 구함

다음단계의 최대값은 전단계 최대값들+현재값 값들과 현재값을 굳이 더하지않은경우중에 더 큰것을 택함

 

구현후 제출

import sys
input=sys.stdin.readline

N=int(input())
a=int(input())
b=int(input())
d=[(0,0),(a,a),(b,a+b)]
for i in range(N-2):
    c=int(input())
    # 연속수가 아닌경우, 연속수인경우
    d.append( (max(c+d[-2][0], c+d[-2][1], d[-1][0], d[-1][1]), c+d[-1][0]) )
print(max(d[-1]))

 

끝까지 가는듯 싶다가 value에러가 뜸 

 

원인이뭐지.. 도무지 감히 잘 안잡힌다

시도1

리스트-튜플 구조에서 2중 리스트로 바꿔본다

또다시뜨는 value에러 뭔가를 놓치고 있는게 분명하다

밸류에러는 주로 숫자가 아닌것을 int형으로 바꾸려고 한다던가

 

도저히 모르겠어서 질문검색

런타임 에러문제를 가지신 질문자의 질문 발견 나와 비슷한것같다

답변은 N=1일때 제대로된 값을 출력할수없다는것

 

아 그게 문제였군 바보같았다 ㅋㅋ

동적계획법문제에서는 결과값 출력할때

항상 d[N]으로 출력될수있게끔 하는게 좋은 습관일것같다

 

제출

import sys
input=sys.stdin.readline

N=int(input())
a=int(input())
b=int(input())
d=[[0,0],[a,a],[b,a+b]]
for i in range(N-2):
    c=int(input())
    d.append( [max(c+d[-2][0], c+d[-2][1], d[-1][0], d[-1][1]), c+d[-1][0]] )
print(max(d[N]))

또다시뜬 밸류에러 

 

생각해보니 첫 input()값도 N이 1일경우 받지않는다 이부분도 수정

 

제출

import sys
input=sys.stdin.readline

N=int(input())
a=int(input())
if N>1:
    b=int(input())
    d=[[0,0],[a,a],[b,a+b]]
    for i in range(N-2):
        c=int(input())
        d.append( [max(c+d[-2][0], c+d[-2][1], d[-1][0], d[-1][1]), c+d[-1][0]] )
    print(max(d[N]))
else:
    print(a)

정답

 

코드는 다구해놓고 사소한부분?을 실수해서 아쉬운문제였다

졸려서 그런거겠지? 하하(밤을샌 상태)