Coding Test/DP

[2011] 암호코드

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] 동전 바꿔주기 (DP)

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(3차원 DP)

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번] 고층 빌딩 (빌딩 순서 구하기, 3차원 DP)

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) ← 보이는 갯수 동일, 가..

[1915번] 가장 큰 정사각형

1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 1로 된 가장 큰 정사각형의 크기 출력 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 import sys input=sys.stdin.readline n,m=list(map(int, input().split())) d=[[0 for j in range(1001)] for i in range(1001)] max=0 # 변의 길이 for i in range(0,n): # 세로 arr=list(input()) for j in range(0,m): # 가로 d[i][j]=int(arr[j]) if d[i][j]==1 and j>..

[13398번] 연속합2 (한개 수 삭제)

13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 분석 L[N] : 왼쪽에서부터 N을 포함한 최대 연속 합 L[i]= max(A[i], L[i-1]+A[i]) R[N] : 오른쪽에서부터 N을 포함한 최대 연속 합 R[i]= max(A[i], R[i+1]+A[i]) L[N-1] + R[N+1] : N을 1개 제거한 최댓값 (1개의 수를 삭제할 수 있기 때문) [1912번] 연속합 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 ..

[1912번] 연속합

1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 n = int(input()) list = list(map(int, input().split())) dp = [0] * n # 최대 연속합 dp[0] = list[0] for i in range(1, n): dp[i] = max(list[i], dp[i-1]+list[i]) # list[i] / 이전최대연속합 + list[i] # print(dp) print(max(dp))

[10844번] 쉬운 계단 수(2차원 DP)

10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 분석 D[N][H] : 길이가 N인 계단에서 H높이로 종료되는 계단 수를 만들 수 있는 경우의 수 D[i][0] : 0인 경우, 뒤에 1만 올 수 있음 ➔ D[i][1] D[i][j] : 1~8인 경우, -1, +1 높이 올 수 있음 ➔ dp[i][j]= dp[i-1][j-1] + dp[i-1][j+1] D[i][9] : 9인 경우, 뒤에 8만 올 수 있음 ➔ D[i][8] 풀이 import sys input=sys.stdin.readline # 길이 n=int(input()) # dp[계단길이][계단높이] dp=[[0 for j in range(11)] for i in ran..

[11726번] 2×n 타일링

11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 분석 D[N] : 길이 N으로 만들 수 있는 타일의 경우의 수 D[N-1] : n-1까지 타일이 채워져있는 경우 ➔ 새로운 타일 1개를 채워 N길이를 만듦 D[N-2] : n-2까지 타일이 채워져있는 경우 ➔가로로 타일 2개를 래워 N길이를 만듦 D[N] = D[N-1]+D[N-2] 풀이 # 2*n크기 직사각형을 2*1/1*n으로 채우는 방법의 수 n = int(input()) d=[0]*1001 # n의 최댓값 1000 d[1]=1 d[2]=2 for i in range(3, n+1..

[14501번] 퇴사

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net bottom up n = int(input()) s = [list(map(int, input().split())) for i in range(n)] dp = [0 for _ in range(n+1)] for i in range(n): for j in range(i+s[i][0], n+1): if dp[j] < dp[i] + s[i][1]: dp[j] = dp[i] + s[i][1] print(dp[-1]) top down n = int(input()) dp = [0]*(n+2) # 오늘부터 퇴사일까지 벌수있는 최대수입 (점화식 테이블) t=[0]*(n+1) # 상담에 필요한 일수 p=[0]*(n+1)..