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

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의 자리 수까지 다 구하고 ..

1. 접근 단순하게 생각했을 때 새로운 n번째 타일을 채울 때는 n - 1번째 타일들에 세로 직사각형 1개가 추가되는 것을 생각할 수 있었습니다. 나머지 경우의 수를 생각해보았을 때 방금 추가한 세로 직사각형이 중간에 들어갈 수 있기 때문에 상상만으로 접근하기에는 어려웠습니다. 2. 해결 그림을 그려 규칙을 찾아보는 것으로 하였습니다. 2 x 1 2 x 2 2 x 3 - 2 x 2 타일에 세로 직사각형 타일 추가 - 2 x 1 타일에 가로 두 개 타일, 정사각형 타일 추가 2 x 4 - 2 x 3 타일에 세로 직사각형 타일 추가 - 2 x 2 타일에 가로 두 개 타일, 정사각형 타일 추가 즉 n번째 타일의 경우의 수는 (n - 1번째 타일의 경우의 수) + (n - 2번째 타일의 경우의 수의 두 배) 3..