[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]의 결과 값 중 최소값..
[Baekjoon] 백준 3055번 탈출 3055번 탈출 문제 풀이 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다. 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으..

티스토리툴바