문제 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 풀이 카드 구매하기에서는 구매하고자 하는 카드를 최대값으로 구매하는 문제였다. 이와 달리 카드 구매하기 2는 가장 최소 값으로 카드를 구매할 경우에 발생하는 금액을 반환하는 문제이다. 카드 구매하기와 동일한 방법으로 풀며, 약간의 코드를 수정하면 이 문제도 쉽게 풀 수 있다. 코드 if __name__ == '__main__': N = int(input()) card = [0] + list(map(int, input().split())) memo = [0]..
문제 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..
