분류 전체보기
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-..
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