https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제의 조건 - 0과 1로만 이루어진 수를 이진수라고 한다. - 다음 조건을 만족하면 이친수라고 한다. 1. 이친수는 0으로 시작하지 않는다 2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. - N자리 이친수의 개수를 구하는 문제 d = [0]*91 n = int(input()) d[1] = 1 d[2] = 1 for i in range(..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제의 조건 - 인접한 자리의 차이가 1이 나는 수를 계단 수라고 한다. - 예 : 45656 - 길이가 N인 계단 수의 개수를 구하는 문제 D[i][j] = 길이가 i이고 마지막 숫자가 j인 계단 수의 개수 D[i][j] = D[i-1][j-1] + D[i-1][j+1] ( 1

https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제의 조건 - 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제 - 단 같은 수를 두 번 이상 연속해서 사용하면 안된다. - n=4 - 1+2+1 - 1+3 - 3+1 * 조건 때문에 점화식을 그대로 사용할 수 없다. -> 그 조건을 점화식에 넣기 D[i][j] = i를 1, 2, 3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 j ... + 1 = i -> D[i][1] = D[i-1][2] + D[i-1][3] .....

https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제의 조건 - 카드 N개를 구매해야 한다. - 카드팩은 총 N가지 종류가 존대한다. - i번째 카드팩은 i개의 카드를 담고 있고, 가격은 P[i]원이다. - 카드 N개를 구매하는 비용의 최소값을 구하는 문제 n = int(input()) card = [0] card += list(map(int, input().split())) dp = [0 for _ in range(n+1)] dp[1] = car..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net [문제의 조건] 1. 카드 N개를 구매해야 한다. 2. 카드 팩은 총 N가지 종류가 존재한다. 3. i번째 카드팩은 i개의 카드를 담고 있고, 가격은 P[i]이다. 4. 카드 N개를 구매하는 비용의 최대값을 구하는 문제이다. D[N] =카드 N개를 구매하는 최대 비용 = max(D[N-i] + P[i]) (1

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 이 문제는 이전에 풀었던 11276 2*n 타일링 문제에서 조건이 추가된 문제이다. 이전에는 마지막에 두 가지 경우가 올 수 있었으나, 이 문제의 경우에는 세가지 경우가 올 수 있다. 그러므로 이 문제의 점화식은 D[n] = D[n-1] + D[n-2] * 2 이다. n = int(input()) D = [0 for _ in range(n+1)] if n == 1: print(n) elif n==2: print(n+1) els..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 2*n 직사각형을 1*2, 2*1 타일로 채우는 방법의 수 D[n] = 2 X n 직사각형을 채우는 방법의 수 2*n 직사각형이 있을 때, 가장 오른 쪽에 타일을 놓을 수 있는 방법은 총 2가지가 있다. 1) 세로 블록이 하나 오는 경우 : D[n-1] 2) 가로 블록 두개 오는 경우 : D[n-2] D[n] = D[n-1] + D[n-2] 2*5의 경우 수는 (1) 2*3경우에서 블록 두 개를 더 붙이는 것과 (2)..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이 문제는 큰 문제를 작은 문제를 통해 풀 수 있으므로 DP를 이용해 풀 수 있다. 예를 들어보면, 4가 입력 되었을 때 4 -> 2 -> 1 이므로 정답은 2가 된다. 이번에는 12가 입력된다면 12/3 = 4이므로 4를 입력으로 했을 때의 정답에서 1을 더하면 된다. 이와 같이 이 문제는 작은 문제들을 통해 큰 문제를 해결 할 수 있다. 또한 큰 문제를 작은 문제로 쪼갤 수 있다. D[N] = N을 1로 만드는 최소 연산 횟수 n = int(input()) dp = [0] * (n+1) dp[1] = 0 f..

1. Overlapping Subproblem - 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다. - 문제를 작은 문제로 쪼갤 수 있다. 2. Optimal Substructure - 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다. 3. Dynamic Programming - 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다. - 정답을 어딘가에 메모해놓는다. => Memoization - 모든 문제를 풀어야 한다. - 모든 문제는 1번만 플어야한다. - 두 가지 구현방식 1. Top-down : 큰 문제를 작은 문제로 나누어서 풀어간다(재귀) 2. Botton-up : 가장 작은 문제를 통해서 큰 문제를 풀어간다(반복문) 4. 다이나민 문제 풀이 전략 글로 점화식의 정의를 세운..

www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 최대 숫자가 20까지이므로 DP 테이블을 만들어 풀면 금방 끝낼 수 있다. 최대 숫자가 20이라 했으므로 행이 0부터 20까지 있고, 열이 n개 있는 DP 테이블을 생성한다. 계산해서 나온 값을 차례대로 DP 테이블에 기록한다. 이때 그냥 기록하는게 아닌 경우의 수를 기록해야한다. import sys input=sys.stdin.readline n=int(input()) dp=[[0 for _ in ra..