[Baekjoon] 백준 10844번 쉬운계단수 10844번 쉬운계단수 문제 풀이 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 예제 입력 1 2출력 9 17코드 #include using namespace std; int d[101][10]; const long long mod = 1000000000; int main() { int n..
[Baekjoon] 백준 11052번 카드구매하기 11052번 카드구매하기 문제 풀이 문제 카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다. 민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다. 예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.카드 팩의 가격이 주어졌을 때, ..
[Baekjoon] 백준 9095번 1,2,3 더하기(다이나믹프로그래밍) 9095번 1,2,3 더하기 문제 풀이 문제 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. '4' 입력 시 나타낼 수 있는 방법 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 예제 입력 3 4 7 10출력 7 44 274코드 #include #include using namespace std; int d[12]; int top_down(int n) { if (n == 0) r..
[Baekjoon] 백준 11727번 2xn타일링2 11762번 2xn타일링 문제 풀이 문제 2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 예제 입력 2 3 12출력 3 171 2731코드 #include #include using namespace std; int d[1001]; int n; void bottom_up(int n) { for (int i = 2; i 0) return d[n]; d[n] = top_down(n - 1) + (2 * top_down(n - 2)); return d[n] %= 10007; } int main() { cin ..
[Baekjoon] 백준 11762번 2xn타일링 11762번 2xn타일링 문제 풀이 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 예제 입력 2 9출력 2 55코드 #include #include #include using namespace std; int d[1001]; int n; int top_down(int n) { if (n == 0) return 1; if (n == 1) return 1; if (d[n] > 0) return d[n] %= 10007; d[n] = top_down(n - 1) + top_down(n - 2);..
[Baekjoon] 백준 1463번 1로만들기 Top-down int top_down(int n) { if (n == 1) return 0; if (d[n] > 0) return d[n]; d[n] = top_down(n - 1) + 1; if (n % 2 == 0) { int temp = top_down(n / 2) + 1; if (d[n] > temp) d[n] = temp; } if (n % 3 == 0) { int temp = top_down(n / 3) + 1; if (d[n] > temp) d[n] = temp; } return d[n]; } 큰 문제를 작은 문제로 나누어서 풀이한 후 큰 문제의 정답을 알아내는 방법이다. 즉 n이 6인경우를 구할 때 d[6]을 알기 위해서는 작은 결과값인 d[5], d[4], d[2]의 결과 값 중 최소값..

티스토리툴바