PS
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-..
BOJ 9095 1, 2, 3 더하기
boj 9095 1, 2, 3 더하기 D[i] = 정수 i를 1, 2, 3의 합으로 나타내는 방법의 수라고 하자. 앞 부분은 겹치는 부분이므로 맨 마지막에 올 수 있는 1, 2, 3의 경우만 살펴보면 된다. n = n-1 + 1 -> n-1을 1, 2, 3 합으로 만드는 방법들을 나열하고 각 끝에 1을 붙이는 경우 n = n-2 + 2 -> n-2를 1, 2, 3 합으로 만드는 방법들을 나열하고 각 끝에 2를 붙이는 경우 n = n-3 + 3 -> n-3을 1, 2, 3 합으로 만드는 방법들을 나열하고 각 끝에 3을 붙이는 경우 D[i]는 위 세 가지 경우의 합이다. 그러므로 점화식을 D[i] = D[i-1] + D[i-2] + D[i-3]로 설정하고 구현한다. #include using namespac..
BOJ 11727 2xN 타일링 2
boj 11727 2xN 타일링 2 boj 11726 2xN 타일링 문제에서 2x2 타일이 추가된 경우이다. 똑같은 방식으로 테이블 D[i] = 1x2, 2x1, 2x2 타일로 채우는 경우의 수 라고 정의한다. 이 때, 다른 점은 끝에 2칸을 채우는 방법이 2x1 타일 2개를 이용하는 방법과 2x2 타일을 이용하는 방법으로 2가지이다. 그러므로 점화식으로D[i] = D[i-1] + 2xD[i-2] 를 설정하고 구현한다. #include using namespace std; int n; int D[1005]; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; D[1] = 1; D[2] = 3; for (int i = 3; i
BOJ 11726 2xN 타일링
boj 11726 2xN 타일링 간단한 DP 문제이다. DP가 무엇인지를 다시 생각해보면, 하위 문제들을 먼저 푼 후 그것들을 쌓아올려 주어진 문제를 해결하는 알고리즘이다. DP 문제를 풀 때 중점은 테이블을 정의해주고, 그 테이블의 제일 하위 값들이 무엇일까를 생각하며 점화식을 찾는 것이다. 먼저 테이블 설정을 해보면, D[i] = 1x2, 2x1 타일로 채우는 경우의 수 라고 정의하자. 전체 경우의 수 D[i]는 아래 그림과 같이 맨 끝의 한 칸을 1x2 타일이 채우는 경우와 맨 끝의 두 칸을 2x1 타일 2개가 채우는 경우 2가지로 나뉜다. 맨 끝이 3칸이 남는 경우는 더 채우면 결국 앞의 2가지와 겹치기 때문에 생각할 필요가 없다. 그러므로 점화식을 D[i] = D[i-1] + D[i-2]로 설정..