https://www.acmicpc.net/problem/16400[BOJ] 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..
문제풀이/DP
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자..
https://www.acmicpc.net/problem/14925 풀이점화식: `dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1`dp[i][j]는 현재 위치(빨간색).왼쪽(노란색), 위쪽(파란색), 대각선 왼쪽 위(검은색) 방향의 dp 값들을 확인한다.이 세 값 중 최솟값에 1을 더한다.그림에서 'a'로 표시된 부분들은 기존에 만들어진 정사각형의 변을 나타내고, '1'로 표시된 부분은 새로 추가되는 1칸을 의미한다.이렇게 세 방향의 최솟값을 사용하는 이유는 정사각형이 되려면 세 방향 모두가 정사각형의 일부가 되어야 하기 때문이다. 만약 세 방향 중 하나라도 작은 값이 있다면, 그 방향으로는 더 큰 정사각형을 만들 수 없다. 따라서 가능한 최대 정사각..
