![]()
https://school.programmers.co.kr/learn/courses/30/lessons/12913코드function solution(land) { let answer = 0; const n = land.length; const dp = Array.from(new Array(n), ()=>new Array(4).fill(0)); for(let i = 0;i 땅따먹기는 행을 하나씩 차례로 밟으면서 내려와야 한다. 그 말은 k번째 행으로 오기 위해서는 k-1행을 무조건 거쳐야 한다는 말이다. 이런 경우에는 이전에 저장된 값을 이용하여 연산 횟수를 줄이는 DP(Dynamic Programming)을 사용하면 시간 복잡도를 작게 만들어서 풀 수 있다. 2차원 배열 `dp`는..
https://www.acmicpc.net/problem/16400코드n = int(input())def prime_number(n): is_prime = [True]*(n+1) is_prime[0] = False is_prime[1] = False prime = [] for i in range(2, n+1): if is_prime[i]: for j in range(i*2, n+1, i): is_prime[j] = False prime.append(i) return primeprime = prime_number(n)dp = [0]*(n+1)dp[0] = 1for p in prime: for..
https://www.acmicpc.net/problem/14267코드import sysinput = sys.stdin.readlinen, m = map(int, input().split())boss = [0]+list(map(int, input().split()))compliments = [0]*(n+1)for _ in range(m): i, w = map(int, input().split()) compliments[i] += wfor i in range(2, n+1): compliments[i] += compliments[boss[i]]print(*compliments[1:]) 해당 문제는 트리디피 알고리즘으로 풀 수 있는 문제에 속하긴 하지만, 문제의 조건이 쉬워서 DP만으로도 풀 ..
![]()
https://www.acmicpc.net/problem/17208코드import sysinput = sys.stdin.readlinen, m, k = map(int, input().split())orders = []for _ in range(n): x, y = map(int, input().split()) orders.append((x, y))dp = [[[0]*(k+1) for _ in range(m+1)] for _ in range(n+1)]answer = 0for order_idx in range(1, n+1): now_burger, now_fry = orders[order_idx-1] for burger in range(m+1): for fry in range(..
![]()
https://www.acmicpc.net/problem/11057코드n = int(input())dp = [[0]*10 for _ in range(n+1)]# 초기화for i in range(10): dp[1][i] = 1# DPfor i in range(2, n+1): dp[i][0] = 1 for j in range(1, 10): dp[i][j] = dp[i-1][j]+dp[i][j-1]print(sum(dp[n]) % 10007) N자리 오르막 수의 개수는 DP를 이용하면 많은 시간을 들이지 않고도 구할 수 있다.N자리 오르막 수는 (N-1)자리 오르막 수에서 가장 오른쪽의 수와 같거나 그보다 큰 수를 오른쪽에 하나 붙이면 만들 수 있다. 예를 들어, 1234라는 4자..
