백준 2156번 포도주 시식 Python

🔷 포도주 시식 (백준 2156번)

✅ 문제 설명

포도주 시식회에 온 효주는 테이블 위에 일렬로 놓여있는 포도주 잔 중에서 포도주를 마시려고 합니다. 각 포도주 잔에는 일정한 양의 포도주가 들어있으며, 다음 두 가지 규칙이 있습니다.

• 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하며, 마신 후에는 다시 원래 위치에 놓아야 합니다.
• 연속으로 놓여 있는 3잔을 모두 마실 수는 없습니다.

효주는 가능한 한 많은 양의 포도주를 마시고자 합니다. 각 포도주 잔에 들어있는 양이 주어졌을 때, 최대 몇 리터의 포도주를 마실 수 있는지 계산하는 프로그램을 작성해야 합니다.

---

✅ 문제 조건 및 입력

• 입력 첫째 줄에 포도주 잔의 개수 n (1 ≤ n ≤ 10,000)
• 다음 n줄에 각 포도주 잔에 들어있는 포도주의 양이 주어집니다. (포도주 양은 0 이상 1,000 이하의 정수)
• 출력: 최대로 마실 수 있는 포도주 양을 출력합니다.

---

✅ 예제

예제 입력 1

6
6
10
13
9
8
1

예제 출력 1

33

예를 들어 위 예제에서 6개의 포도주 잔에 들어있는 양은 각각 6, 10, 13, 9, 8, 1입니다. 효주는 첫 번째, 두 번째, 네 번째, 다섯 번째 잔을 선택해서 마시면 총 33 리터를 마실 수 있습니다.

---

✅ 문제 설명 상세

• 포도주 잔을 마실 때는 한 잔을 골라 그 안에 든 포도주를 전부 마셔야 합니다.
• 잔은 다시 자리에 놓기 때문에 포도주 잔을 "먹는 것"과 "위치에서 사라지는 것"은 다릅니다. 즉, 순서와 개수는 변하지 않습니다.
• 가장 중요한 제한은 연속으로 3잔을 마시는 것이 금지되어 있다는 점입니다.
• 즉, 세 잔 연속으로 고르면 안 됩니다.

예를 들어 포도주 양이 [6, 10, 13, 9, 8, 1] 일 때,

• 만약 1, 2, 3번째 잔을 모두 마시면 연속 3잔을 마셨으므로 불가능합니다.
• 1, 2, 4, 5번째 잔을 마시면 연속 3잔이 아니면서 포도주 양의 합이 최대가 됩니다.

---

✅ 아이디어

---

📝 1. 문제 이해

우리는 최대한 많은 포도주를 마셔야 합니다. 단, 중요한 규칙이 있습니다.

"세 번 연속으로 포도주를 마실 수 없습니다."

즉, 연속해서 한 잔이나 두 잔은 괜찮지만, 연속으로 세 잔을 마시는 것은 절대 불가능합니다.

---

📝 2. 초기 데이터 설정

• 포도주 양(arr)과 dp 배열 초기 설정:

arr = [6, 10, 13, 9, 8, 1] 
dp = [6, 16, 0, 0, 0, 0] 

• 첫 번째 잔만 마실 때 최댓값: dp[0]=6
• 두 잔 모두 마실 때 최댓값: dp[1]=6+10=16

여기까지는 세 잔 연속 조건이 없으므로 간단히 연속해서 마시면 됩니다.

---

📝 3. 세 번째 잔을 고려하기

세 번째 잔(13)을 고려합니다. 단순히 더하면:

arr = [6, 10, 13, 9, 8, 1] 
dp = [6, 16, 29, 0, 0, 0] → 잘못된 값

이렇게 하면 포도주를 OOO로 세 번 연속 마셔서 규칙 위반입니다.

🎬 가능한 경우를 OX로 다시 분석:

6 10 13
O O X → 6+10=16
O X O → 6+13=19
X O O → 10+13=23 ✅(최대)

여기서는 XOO=23이 최대입니다. 따라서 업데이트:

dp = [6, 16, 23, 0, 0, 0] 

---

📝 4. 네 번째 잔을 고려하기(중요한 시점)

이제 네 번째 잔(9)을 고려할 때는 더 복잡해집니다.

• 세 잔을 기준으로 보면 가능한 조합은 3가지:

10 13 9
O O X
O X O
X O O

하지만 이제 네 번째 잔을 포함하면, 1번 잔까지 포함되어 더 많은 경우가 발생합니다.

6 10 13 9
? O O X
? O X O
? X O O

이때 '?'는 1번 잔이 마셔졌는지 안 마셔졌는지입니다. 이 모든 걸 기억할 수 없으므로 dp 배열을 이용해서 해결합니다.

---

🚨 의문점

dp 배열은 단순히 숫자만 저장합니다. 그 값이 연속해서 만들어졌는지, 아니면 연속하지 않았는지 알 수 없습니다. 그래서 연속성을 따로 추적하지 않고도 3연속을 방지할 방법을 생각합니다.

---

✅ 해결책 (상세하고 명확한 설명)

dp 배열의 연속 여부를 무시하고, 다음 세 가지 경우로 나누어 해결합니다.

• [경우1] dp[N] = dp[N-1]
• [경우2] dp[N] = dp[N-2] + arr[N]
• [경우3] dp[N] = dp[N-3] + arr[N-1] + arr[N]

세 가지 경우를 왜 선택하는지, 각각 왜 3연속 방지를 보장하는지 명확한 예시로 하나씩 보여드립니다.

---

🎬 [경우1] dp[N] = dp[N-1] (N번째 잔을 마시지 않음)

이 경우는 N번째 잔을 안 마십니다. dp[N-1]의 값이 1잔 연속이든, 2잔 연속이든 상관없이 더 이상 추가로 마시지 않기 때문에 3연속은 발생할 수 없습니다.

예시	N-3	N-2	N-1	N
연속2잔에서 중단	X	O	O	X
연속1잔에서 중단	O	X	O	X
연속되지 않음	X	X	O	X

모두 N번째는 마시지 않으므로, 3연속 불가능이 명확히 보장됩니다.

---

🎬 [경우2] dp[N] = dp[N-2] + arr[N] (N번째 마시고, N-1번째 안 마심)

이 경우는 N번째는 마시고(N:O), N-1번째는 안 마십니다(N-1:X). 여기서 핵심은 N-1번째를 건너뛰는 것입니다.

예시	N-3	N-2	N-1	N
가능	O	O	X	O
가능	X	O	X	O
가능	O	X	X	O

이 경우들은 N-1번째 잔이 모두 X이므로, 아무리 이전에 연속으로 마셨다고 해도 중간에서 반드시 끊어져서 3연속은 불가능합니다. 따라서 이 경우도 반드시 3연속 방지가 됩니다.

---

🎬 [경우3] dp[N] = dp[N-3] + arr[N-1] + arr[N] (N, N-1번째 마시고, N-2번째 안 마심)

이 경우는 N번째(N:O)와 N-1번째(N-1:O)를 마시고, N-2번째 잔을 건너뜁니다(N-2:X).

예시	N-3	N-2	N-1	N
가능	O	X	O	O
가능	X	X	O	O
불가	O	O	O	O

만약 N-2번째를 안 건너뛰고 OOO라면 위반이지만, 반드시 N-2번째를 건너뜁니다(N-2:X). 즉 중간이 무조건 끊어지므로 3연속 불가를 명확히 보장합니다.

---

🔍 이 방식의 최종 코드

N=int(input())

arr=[0 for _ in range(N+1)]
dp=[0 for _ in range(N+1)]

for i in range(1,N+1):
    arr[i]=int(input())

dp[1]=arr[1]
if(N>=2):
    dp[2]=arr[1]+arr[2]


for i in range(3,N+1):
    dp[i]=max(
        dp[i-1],
        dp[i-2]+arr[i],
        dp[i-3]+arr[i-1]+arr[i]
    )

print(dp[N])

• dp[0], dp[1], dp[2]는 초기 설정됩니다.
• dp[i]는 세 가지 경우 중 최대를 선택합니다.
• 세 경우는 위에서 설명한 대로 명확하게 3연속 방지를 보장합니다.

---

🍷 전체 코드

N=int(input())

arr=[0 for _ in range(N+1)]
dp=[0 for _ in range(N+1)]

for i in range(1,N+1):
    arr[i]=int(input())

dp[1]=arr[1]
if(N>=2):
    dp[2]=arr[1]+arr[2]


for i in range(3,N+1):
    dp[i]=max(
        dp[i-1],
        dp[i-2]+arr[i],
        dp[i-3]+arr[i-1]+arr[i]
    )

print(dp[N])

---

🍷 개별 코드 설명 (도식화 포함)

✅ 입력 부분

N=int(input())

arr=[0 for _ in range(N+1)]
dp=[0 for _ in range(N+1)]

for i in range(1,N+1):
    arr[i]=int(input())

• 입력을 받기 위한 코드입니다.
• 포도주 잔의 개수를 N으로 입력받고, 각각의 포도주 양을 배열 arr에 저장합니다.
• 배열을 1부터 N까지 사용합니다.

도식화 예시

N=6

입력: 6 10 13 9 8 1

arr배열:

arr[1] arr[2] arr[3] arr[4] arr[5] arr[6]

6 10 13 9 8 1

---

✅ 초기 dp값 세팅

dp[1]=arr[1]
if(N>=2):
    dp[2]=arr[1]+arr[2]

• 초기값을 설정하는 부분입니다.
• 첫 번째 잔은 무조건 마시고, 두 번째 잔까지는 연속으로 마시는 것이 항상 최대이므로 이렇게 초기화합니다. N >= 2 조건은 N이 1일 경우 dp[2]에 접근하여 발생하는 런타임 에러를 방지하기 위함입니다.

도식화 예시

dp[1] = arr[1] = 6

dp[2] = arr[1] + arr[2] = 6 + 10 = 16

dp배열 상태:

dp[1] dp[2] dp[3] dp[4] dp[5] dp[6]

6 16 0 0 0 0

---

✅ 핵심 DP 점화식 (세 가지 경우)

for i in range(3,N+1):
    dp[i]=max(
        dp[i-1],
        dp[i-2]+arr[i],
        dp[i-3]+arr[i-1]+arr[i]
    )

• 포도주를 마시는 규칙(3잔 연속 마실 수 없음)을 보장하기 위한 세 가지 경우를 비교하는 부분입니다.

식	의미
dp[i - 1]	i번째 잔을 안 마시는 경우
dp[i - 2] + arr[i]	i번째 잔만 마시고, (i-1)번째 잔은 안 마시는 경우
dp[i - 3] + arr[i - 1] + arr[i]	i번째, (i-1)번째 잔을 연속해서 마시고 (i-2)번째 잔은 안 마시는 경우

도식화 예시 (i=4일 때)

i=4

arr: 6 10 13 9

① dp[i-1]=dp[3]=23 (4번째 잔 X)

O X O X (합=6+13=19)

X O O X (합=10+13=23)

② dp[i-2]+arr[i]=dp[2]+arr[4]=16+9=25 (4번째 잔 O, 3번째 잔 X)

O O X O (합=6+10+9=25)

③ dp[i-3]+arr[i-1]+arr[i]=dp[1]+arr[3]+arr[4]=6+13+9=28 (4번째 O, 3번째 O, 2번째 X)

O X O O (합=6+13+9=28)

비교: max(23, 25, 28)=28

따라서 dp[4]=28

이렇게 점화식을 통해 모든 경우를 반복하여, 자동적으로 3연속 방지가 보장됩니다.

---

✅ 결과 출력 부분

print(dp[N])

• 최종적으로 포도주 잔의 개수 N까지의 최대값인 dp[N]을 출력합니다.

도식화 예시 (N=6일 때 최종 결과)

dp배열 상태:

dp[1]=6

dp[2]=16

dp[3]=23

dp[4]=28

dp[5]=33

dp[6]=33

따라서 dp[N]=dp[6]=33

최종 출력: 33

---

🍷 결론

• 동적 계획법(DP)은 "작은 문제의 해답을 활용해 큰 문제를 해결하는 방식"이며, 포도주 시식 문제에서 매우 효율적입니다.
• dp 배열은 숫자만 저장할 뿐이지만, 특별한 점화식 설계(세 가지 경우)를 통해 연속성을 직접 체크하지 않고도 자동적으로 3잔 연속 금지를 보장합니다.
• 각각의 경우가 왜 3연속 금지를 보장하는지는, dp식에서 '중간 잔을 마시지 않음(X)'으로써 무조건 중간에 끊기게끔 설계되었기 때문입니다.
• 즉, 이 문제는 각각의 단계에서 가능한 세 가지 경우를 꼼꼼히 비교하고, 이전 결과(dp)를 활용함으로써 효율적이고 간편하게 해결됩니다.