[python/2156]포도주 시식

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

이 문제는 점화식을 이용하여 풀면 되는 문제입니다.

 

문제 풀이를 보시려면 더보기를 클릭하시면 됩니다.

포도주 시식

이 문제에서 중요한 점은 2번째 규칙입니다.

 

2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

 

잔의 수를 늘려가면서 문제에 접근해 보도록 하겠습니다.

여기서 list는 포도주 잔에 들어있는 포도주의 양이 들어있는 리스트입니다.

잔의 수 3과 4를 자세히 보면 다음과 같습니다.

잔이 3개 일 때 만약 a가 최댓값이라면 잔이 4개일 때는 a + list[3]이 최댓값이 될 것이고, b가 최댓값이라면 b + list[3]이 최댓값이 될 것입니다. 만약 c가 최댓값이라면 4에서는 3개의 값을 비교해봐야 합니다. 

이것을 보고 이 문제는 점화식으로 접근해야 하는 것을 알 수 있습니다.

포도주가 3개 미만일 경우도 잊지 않고 예외처리를 해주어야 합니다.

 

전체 코드

# 백준 2156 포도주 시식
def solve(wine):
    # 점화식 과정을 담을 list 생성
    answer = [0 for _ in range(len(wine))]
    # index 1의 초기값을 입력 받은 리스트 값의 0으로 설정
    answer[0] = wine[0]
    # 입력 받은 리스트의 길이가 1개이면 answer[1] 반환
    if len(wine) < 2:
        return answer[0]
    # index 2의 초기값을 입력 받은 리스트 0과 1의 합으로 설정
    answer[1] = wine[0] + wine[1]
    # 입력 받은 리스트의 길이가 2이면 answer[2] 반환
    if len(wine) < 3:
        return answer[1]
    # 입력 받은 리스트의 길이가 3이상이면 answer의 마지막 값을 반환
    for i in range(2, len(wine)):
        answer[i] = max(answer[i - 1],
                        answer[i - 2] + wine[i],
 # i가 2일때는 answer[-1]의 값을 가져오게 되는데 이 값은 0으로 초기화 되어 있음
                        answer[i - 3] + wine[i - 1] + wine[i])
    # 마지막 값 반환
    return answer[-1]
 
if __name__=='__main__':
    wine = []
    for i in range(int(input())):
        wine.append(int(input()))
    print(solve(wine))