Cracking Code

1. 접근 단순히 대각선으로, 그리고 순차적으로 오른쪽 방향으로 점점 숫자를 쌓아나가 n 번째 스티커 2장을 비교하여 출력하면 될 줄 알았습니다. 하지만 꼭 대각선으로 나아가야 한다는 규칙은 없었고 그것이 꼭 최댓값을 출력한다는 보장은 없었습니다. 2. 해결 그럼 도대체 어떻게 최댓값을 구할 수 있을까 생각하는 도중 현재 스티커에 접해 있는 스티커는 사용할 수 없으니 사용할 수 없는 스티커를 제외한 최대의 수를 가질 스티커를 골라서 비교하면 되는 간단한 문제였습니다. n - 1 번째 대각으로 구해오던 수와 그의 바로 뒤쪽에 있는 n - 2 번째 수를 비교하면 최댓값을 구할 수 있었습니다. 3. 코드 import java.io.BufferedReader; import java.io.IOException; ..

1. 접근 규칙에 따라서 가능한 계획법을 짜도록 합니다. 동적계획법에 차근차근 저장할 배열과 입력을 받아 포도주 양을 저장할 배열이 필요했습니다. 동적계획법의 배열은 dp, 포도주 양을 저장할 배열은 arr라고 합시다. 규칙1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주를 모두 마시고 원래 위치에 다시 놓는다. 규칙2. 연속으로 놓여 있는 3잔을 모두 마실 수 없다. 연속으로 3잔을 안 마시기만 하면 됩니다. 차근차근 적어 나가봅니다. dp[1] = arr[1] dp[2] = dp[1] + arr[2] 이제 3잔 째로 갈리게 됩니다. 1번 포도주를 마시고 3번 포도주를 마시는 것과 2번 포도주를 마시고 3번 포도주를 마시는 것 중 더 마시는 것은 무엇인가? dp[3] = Math.max(dp[1] +..