반응형 알고리즘/dynamic programming27 [백준][Python] 10844번 쉬운 계단 수 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 코드 n = int(input()) dp = [[0]*10 for _ in range(n+1)] for i in range(1,10): dp[1][i] = 1 for i in range(2, n+1): for j in range(10): if j == 0: dp[i][j] = dp[i-1][1] elif j == 9: dp[i][j] = dp[i-1][8] else: dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] print(sum(dp[n])%1000000000) 설명 n이 1일 때는 0을 제외한 1~9까지의 숫자가 올 수 있다. n이 2일 때는 앞의 숫.. 2022. 6. 20. [백준][Python] 11660번 구간 합 구하기 5 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 코드 import sys n, m = map(int,input().split()) n_list = [[0] * (n+1)] for _ in range(n): a = [0] + list(map(int,sys.stdin.readline().split())) n_list.append(a) for i in range(1,n+1): for j in range(1,n+1): n_list[i][j] += n_list[i-1][j] +.. 2022. 6. 20. [백준][Python] 2294번 동전 2 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 코드 import sys n,k = map(int,input().split()) cost = [] dp = [10001] * (k+1) dp[0] = 0 for _ in range(n): cost.append(int(sys.stdin.readline().rstrip())) for c in cost: for i in range(1,k+1): if i-c >= 0: dp[i] = min(dp[i-c]+1,dp[i]) if dp[k] !.. 2022. 5. 24. [백준][Python] 14501번 퇴사 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 코드 import sys n = int(input()) T = [0]*(n+2) P = [0]*(n+2) dp = [0]*(n+2) for i in range(1,n+1): T[i],P[i] = map(int,sys.stdin.readline().split()) for i in range(1,n+1): if (i+T[i]) 2022. 5. 23. 이전 1 2 3 4 5 6 7 다음 반응형
