문제 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 풀이 이 문제를 효율적으로 풀기 위해서는 메모이제이션(Memoization)을 활용하여야 한다. 문제의 예제와 같이 1 5 6 7이 입력되는 경우 카드 3개 까지 구매할 수 있는 경우의 수는 다음과 같다. 카드 1개 구매 : 1개 들어있는 카드 팩 카드 2개 구매 : (1개 들어있는 카드 팩) * 2, 2개 들어있는 카드 팩 카드 3개 구매 : (1개 들어있는 카드 팩) * 3, 2개 들어 있는 카드 팩 + 1개 들어 있는 카드백, 3개 들어 있는 카드팩 즉 ..
1, 2, 3 더하기 시리즈 1, 2, 3 더하기 1, 2, 3 더하기 2 1, 2, 3 더하기 3 1, 2, 3 더하기 4 1, 2, 3 더하기 5 1, 2, 3 더하기 6 1, 2, 3 더하기 7 1, 2, 3 더하기 8 1, 2, 3 더하기 9 문제 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 www.acmicpc.net 문제 풀이 이전에 풀었던, 11726 2xn 타일링, 11727 2xn 타일링 2과 같이 어떠한 경우의 수가 있는지 파악하는 것이 중요하다..
백준: 11727 2xn 타일링 2
문제 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 문제 풀이 이 문제는 2 x n 타일링 문제에서 2 x 2 타일이 추가 되어, 사용할 수 있는 타일이 2 x 1, 1 x 2, 2 x 2로 3개인 경우에 2 x n의 공간에 타일을 붙일 수 있는 경우의 수를 구하는 문제이다. 그림 1을 보면, n이 증가함에 따라 1, 3, 5, 11, 21과 같은 규칙을 보이는 것을 알 수 있으며 이를 식으로 나타내면 `f(n) = f(n - 1) + 2 * f(n - 2)`가 된다. 따라서 해당 식을 코드로 작성하면 문제를 해결할 수 있다. 코드 fro..
백준: 11726 2xn 타일링
문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 풀이 세로 타일(2 x 1)과 가로 타일(1 x 2) 타일로 n이 입력될 경우 타일을 붙일 수 있는 경우의 수를 구하는 문제이다. n에 따라 발생할 수 있는 각 경우의 수는 크게 3가지 이다. 모두 세로 타일로 구성 되는 경우 모두 가로 타일로 구성 되는 경우 가로, 세로 타일이 혼합되어 구성되는 경우 타일을 붙일 수 있는 경우의 수는 그림 1과 같다. n에 따른 규칙을 찾아보면 n이 증가함에 따라 1, 2, 3, 5, 8, 13로 증가하는 것을 알 수 있다. 이를 식으로 ..
