Cracking Code

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] +..

1. 접근 이 문제의 경우 각 자리가 오름차순으로 되어 있는지를 확인하여 맞다면 오르막 수라는 조건을 이용해야 했습니다. 그렇기 때문에 "백준 10844: 쉬운 계단 수" 처럼 0 ~ 9의 수를 이용하여 구하는 문제라고 생각했습니다. 2차원 배열을 선언하여 각 n 자리 수일 때마다 끝 자리 수가 0 ~ 9 인 경우를 저장하고 마지막에 다 더하는 것으로 생각했습니다. 끝 자리의 수를 이용하여 생각하면 0은 0 ~ 9를 만들고 1은 1 ~ 9를 만들고 ... 9는 9를 만들 수 있습니다. 그러면 이런 표를 만들 수 있습니다. 2. 해결 위의 표에서 보면 n 자리의 수의 끝 자리가 i 일 경우 n - 1 자리 수 중 i 를 만들 수 있는 수들의 개수 합을 구하면 i 의 개수가 나오게 됩니다. 그러면 결국에는 ..

1. 접근 1자리 수일 경우부터 생각해보기로 했습니다. n = 1 일 때 1, 2, 3, 4, 5, 6, 7, 8, 9의 계단 수가 존재했습니다. n = 2 일 때 10, 12, 21, 23, ... , 98의 계단 수가 존재했습니다. n = 3 일 때 101, 121, 123, 210, 212, 232, 234, ... , 987, 989의 계단 수가 존재했습니다. 즉, 각 계단 수의 끝 자리의 수인 0 ~ 9에 의해 n + 1 자리 수의 계단 수가 추가되었습니다. 그래서 각 끝 자리의 수가 몇 번 나오는가를 저장할 배열이 필요했기에 2차원 배열을 사용하기로 하였습니다. 2. 해결 1부터 n의 자리 수의 끝 자리 수가 몇 번 나왔는지 그 개수를 중첩하여 저장하도록 합니다. n의 자리 수까지 다 구하고 ..