태그:
특정 규칙에 따라 포도주를 마실 때 최대로 마실 수 있는 양을 구하는 문제입니다. 문제의 조건에서 연속 3잔은 마실 수 없다고 되어있습니다. 2579번: 계단 오르기에서는 계단을 연속해서 오르거나 하나 건너뛰어 올라갈 수 있어서 가로 2의 배열을 사용했는데, 여기서는 건너뛰는 거리는 제한이 없습니다. 그렇다고 가로의 길이가 N일 수는 없는 노릇이라 작은 값을 써야 합니다. 하지만 운이 좋게도 문제의 조건에서 포도주의 양은 양수이기 때문에 우리는 가로 3의 배열로 DP를 사용할 수 있습니다. 즉, 3개 이상 건너뛰는 경우는 최대값을 가질 수 없다는 것입니다. 3개 건너뛰는 것보다는 1개 건너뛰고 마시고 1개 건너뛰는 것이 더 많은 양을 마실 수 있는 것이죠. 따라서 가로 3의 배열을 사용하여 조건에 맞게 값을 채우고 끝 줄, 끝에서 두 번째 줄, 끝에서 세 번째 줄의 값들 중 가장 큰 값을 출력하면 됩니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-03-31 22:22:34 |