bottom up """ 현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다. 예를 들어 4m의 네트워크 선이 주어진다면 5가지 방법을 생각할 수 있습니다 1) 1m+1m+1m+1m 2) 2m+1m+1m 3) 1m+2m+1m 4) 1m+1m+2m 5) 2m+2m 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법? 첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다. """ # Bottom-Up n=int(input()) d=[0]*(n+1) d[1]=1 d[2]=2 for i in range(3,n+1): d[i]=d[i-1]+d[i-2] print(d) print(d[n]) top down n=int(input()) d=[0]*(n+1) d[1]=1 d[2]..

2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net """ a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다. 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k(1 ≤ k), 두 번째 줄에 정수 n(n ≤ 14) """ import sys input=sys.stdin.readline d=[[0 for j in range(15)] for i in ra..

2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 분석 10 ≤ 현재 숫자와 바로 그 앞자리 숫자 ≤ 26일 때, 두자리가 가능한 숫자 dp[i] += dp[i-2] : 앞자리 숫자 앞의 DP[현재숫자인덱스-2]에 저장되어있는 값을 DP[현재숫자]에 넣어줌 1 ≤ 현재 숫자 ≤ 9 dp[i] += dp[i-1] : 앞자리 숫자의 DP[앞자리숫자] 또한 DP[현재숫자]에 넣어줌 풀이 code = list(map(int, input())) n = len(code) dp=[0]*(n+1) dp[0]=1 dp[1]=1 if code[0..

2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 www.acmicpc.net 분석 dp[i][j] : i번째 동전까지 사용해서 j원을 만들 수 있는 경우의 수 dp[money] += dp[money - coin * cnt] (money는 구하기 위한 금액, coin은 현재 사용하는 동전의 금액, cnt는 사용하는 동전의 개수) 풀이 """ 입력으로 지폐의 금액 T 동전의 가지 수 k 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1, 2,…, k) 지폐를 동전으로 교환하는 방법의 가지 수 """ t=int(i..

2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 분석 D[N][L][R] : N개의 수열을 수행한 후 왼발의 위치가 L, 오른발의 위치가 R일 때 최소 누적 힘 mp[i][j] : i에서 j로 이동하는데 드는 힘 오른발 : D[N][L][R] = min(D[N-1][L][i] + mp[i][R]) 왼발 : D[N][L][R] = min(D[N-1][i][R] + mp[i][L]) 풀이 import sys input=sys.stdin.readline # N개의 열, L 왼발, ..

1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 분석 D[N][L][R] : N개의 빌딩이 있고 왼쪽에서 볼 때 L개, 오른쪽에서 볼 때 R개가 가능한 경우의 수 가장 작은 빌딩을 N번째로 배치한다고 가정 가장 앞에 배치 : D[N][L][R] = D[N-1][L-1][R] ← 왼쪽에서 보이는 갯수가 +1 가장 뒤에 배치 : D[N][L][R] = D[N-1][L][R-1] ← 왼쪽에서 보이는 갯수가 +1 가운데에 배치 : D[N][L][R] = D[N-1][L][R] * (N-2) ← 보이는 갯수 동일, 가..