문제 링크: https://www.acmicpc.net/problem/2156
난이도: 실버 1
아직 나에게는 너무x100 이해하기 어려운 DP..
패스트캠퍼스 나동빈님 강의에서 i번째 마시기, i번째 안 마시기에서 힌트를 얻고 풀었습니다.
1. dp[1] = wines[1]
2. dp[2] = wines[1] + wines[2]
3. dp[3] = max(dp[2], dp[1]+wines[3], wines[2]+wines[3])
4. dp[4] = max(dp[3], dp[2]+wines[4], dp[1]+wines[3]+wines[4]) ... 이후 반복
const wines = `${require('fs').readFileSync('/dev/stdin')}`.trim().split(/\n/).map(Number);
const n = wines[0];
const dp = [, wines[1], wines[1] + wines[2]];
if (n >= 3) {
dp[3] = Math.max(dp[2], dp[1] + wines[3], wines[2] + wines[3]);
for (let i = 4; i <= n; i += 1) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + wines[i], dp[i - 3] + wines[i - 1] + wines[i]);
}
}
console.log(dp[n]);반례 모음
| 예제 | 반례1 | 반례2 | 반례3 | 반례4 | 반례5 | 반례6 | 반례7 | 반례8 | |
| input |
6
6 10 13 9 8 1 |
6 1 2 3 6 4 1 |
1 0 |
6 100 100 1 1 100 100 |
4 10 10 1 0 |
7
10 100 100 10 10 100 100 |
3 1 1 0 |
10 0 0 10 0 5 10 0 0 1 10 |
6 1 1 0 0 1 1 |
| answer | 33 | 13 | 0 | 400 | 20 | 400 | 2 | 36 | 4 |
아래 글에서도 다른 반례들을 볼 수 있습니다. :)
[백준/2156번/Java] 포도주 시식
문제 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가
raejoonee.tistory.com
'백준' 카테고리의 다른 글
| 백준 알고리즘 - 1697 - 숨바꼭질 - 그래프 문제 풀이 (0) | 2023.08.22 |
|---|---|
| 백준 알고리즘 - 16173 - 점프왕 쩰리 (Small) - 그래프 문제 풀이 (0) | 2023.08.15 |
