코딩고치

1. 문제 주소 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 2. 문제 1, 2, 3 더하기 문제에서 같은 수를 연속해서 더하는 경우를 제외한 경우의 수를 구하는 문제이다. n=4일 때를 보면 1+3, 3+1, 1+2+1 총 3가지 경우이다. 가장 마지막에 더해지는 숫자를 이용하여 2차원 배열을 만들면 d[4][1]=2 (+1로 끝나는 경우의 수) d[4][2]=0 (+2로 끝나는 경우의 수) d[4][3]=1 (+3로 끝나는 경우의 수) 이 된다. n=5일 때 d[5][1] = d[4][2] + d[4][3]이 된다. 1이 연속적으로 더해지는 경우를 제외해..

1. 문제 주소 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 2. 문제 이전 카드 구매하기 문제에서는 n개의 카드를 살 때 금액의 최댓값을 구하는 문제였다. 이 문제는 그 반대로 최솟값을 구하는 문제이다. 최솟값을 구하는 문제기 때문에 초기값 설정에 주의를 해야 한다. [백준][DP] 카드 구매하기 1. 문제 주소 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10..

1. 문제 주소 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 2. 문제 점화식을 세우기 위해 n=2일 때부터 차례대로 구해보았다. 구매하려고 하는 카드의 개수가 4개이고 p={1, 5, 6, 7} 일 때 n=1---p[1] n=2---max(p[2], p[1]+p[2-1]) n=3---max(p[3], p[1]+p[3-1], p[2]+p[3-2]) n=4---max(p[4], p[1]+p[4-1], p[2]+p[4-2],p[3]+p[4-3]) 과 같이 구할 수 있다. 3. 소스 코드 1. Bottom-up 1 2 ..

1. 문제 주소 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 www.acmicpc.net 2. 문제 입력받은 정수 n을 1, 2, 3 세 가지 숫자의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하는 문제이다. n=1일 때부터 표현할 수 있는 방법을 나..