PS/BOJ
BOJ 2156 포도주 시식
boj 2156 포도주 시식 포도주 잔을 마시는 경우를 맨 마지막 포도주 잔의 상태에 따라 나눌 수 있다. 맨 마지막 포도주 잔을 안마시는 경우 맨 마지막 포도주 잔을 마시는데, 그 잔이 연속된 첫번째 잔인 경우 맨 마지막 포도주 잔을 마시는데, 그 잔이 연속된 두번째 잔인 경우 그림으로 표현하면 다음과 같다. arr는 포도주 잔의 양을 담는 배열이고, D[i]는 i번째 잔까지 포도주를 최대로 마시는 양으로 테이블을 정한다. D[i] = D[i-1] D[i] = D[i-2] + arr[i] D[i] = D[i-3] + arr[i-1] + arr[i] 위 세 가지를 비교해서 가장 큰 값을 D[i]로 결정하면 된다. 코드로 구현해보자. #include #include using namespace std; i..
BOJ 9465 스티커
boj 9465 스티커 위 그림과 같이, 문제의 조건에 따라 변을 공유하는 스티커는 뗄 수 없고, 대각으로만 이동하며 뗄 수 있다. 이 때, 대각으로 이동할 수 있는 경우는 아래 그림과 2가지가 있다. 3칸부터는 이동하면 중간에 거쳐갈 수 있는 칸이 무조건 있으므로 가장 높은 점수를 구하는 문제 조건에 어긋나므로 제외한다. 맨 위 그림을 보면, 스티커를 떼는 경로는 마지막에 떼지는 스티커가 첫번째 줄이냐 두번째 줄이냐로 나눠진다. 테이블 D[i][j]는 j번째 줄의 i번째 칸까지 스티커 점수의 최댓값으로 정의하고, score는 스티커의 점수를 담는 배열이다. 그러면 위의 내용을 점화식으로 정의해보자. D[i][0] = max(D[i-1][1], D[i-2][1]) + score[i][0] D[i][1] ..
BOJ 2193 이친수
boj 2193 이친수 쉬운 계단 수, 오르막 수와 비슷한 류의 문제이다. 길이가 N인 이친수의 경우의 수를 끝이 0이거나 1인 경우로 나눈다. 초기 값으로는 길이가 1일 때와 2일 때를 잡고, 그 값을 쌓아올려 길이가 N일 이친수의 갯수를 구한다. 길이가 3 이상인 이친수의 경우, 끝이 0인 경우 그 앞의 수로 0, 1이 올 수 있다. 끝이 1인 경우는 그 앞의 수로 0만 올 수 있다. 이를 바탕으로 테이블 D[i][j]를 길이가 i이고 맨 끝 수가 j인 이친수의 갯수로 정의하고 점화식을 설정했다. j가 0일 때, D[i][j] = D[i-1][j] + D[i-1][j+1] j가 1일 때, D[i][j] = D[i-1][j-1] 점화식을 바탕으로 코드를 구현했다. #include using namesp..
BOJ 11057 오르막 수
boj 11057 오르막 수 길이가 N인 오르막 수의 경우의 수를 어떻게 나눌까. boj 10844 쉬운 계단 수 문제와 비슷하게 끝 자리 수가 0-9 중에 하나인 것은 자명하고, 그러므로 끝 자리 수의 경우로 나누었다. 끝 자리 수가 0이면, 앞에 올 수 있는 수는 0 끝 자리 수가 1이면, 앞에 올 수 있는 수는 0, 1 끝 자리 수가 2이면, 앞에 올 수 있는 수는 0, 1, 2 . . . 끝 자리 수가 9이면, 앞에 올 수 있는 수는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 즉, 길이가 N이고 끝 자리 수가 1인 경우, 앞에 길이가 N-1이고 끝자리 수가 0 이거나 1인 오르막 수가 올 수 있다는 의미이다. 테이블로 D[i][j]는 길이가 i이고 끝 자리 수가 j인 오르막 수의 갯수로 ..
BOJ 10844 쉬운 계단 수
boj 10844 쉬운 계단 수 길이가 N인 계단 수의 경우의 수를 어떻게 나눌 수 있을까. 맨 끝의 숫자가 0~9 중 하나인 것은 자명하다. 맨 끝의 숫자가 0일 경우를 생각해보면, 계단 수이므로 0 앞의 수는 1만 가능하다. 즉, 길이가 N-1이고 끝이 1인 계단 수만이 0 앞에 올 수 있다는 의미이다. 맨 끝의 숫자가 9인 경우는, 9 앞의 수로 8만 올 수 있다. 남은 경우인 맨 끝의 숫자가 1부터 8 사이의 경우는, 각 수에서 1씩 더하거나 뺀 수들이 앞에 올 수 있다. 이 내용을 점화식으로 나타내보자. 테이블로 D[i][j]는 길이가 i이고 맨 끝 수가 j인 계단 수의 갯수라고 한다. j가 0 일 때, D[i][j] = D[i-1][j+1] j가 9 일 때, D[i][j] = D[i-1][j-..