![]()
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칸을 의미한다.이렇게 세 방향의 최솟값을 사용하는 이유는 정사각형이 되려면 세 방향 모두가 정사각형의 일부가 되어야 하기 때문이다. 만약 세 방향 중 하나라도 작은 값이 있다면, 그 방향으로는 더 큰 정사각형을 만들 수 없다. 따라서 가능한 최대 정사각..
https://www.acmicpc.net/problem/13902코드import sysinput = sys.stdin.readlineINF = int(1e9)n, m = map(int, input().split())s = list(map(int, input().split()))wok_set = set(s)dp = [INF]*(n+1)for i in range(m): dp[s[i]] = 1 for j in range(i+1, m): if s[i]+s[j] 로직은 어렵지 않은데 시간 복잡도 줄이기가 정말 어려웠던 문제였다...조건문을 잘 사용해서 필요없는 연산은 최대한 넘어가는 것이 중요하다. 1. 웍으로 한 번에 조리 가능한 경우의 수를 wok_set에 저장할 때 dp에도 1로 ..
https://www.acmicpc.net/problem/27134코드const fs = require("fs");const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";const n = +fs.readFileSync(filePath).toString().trim();function solution(n) { let total = (n * (n + 1)) / 2; if (total % 2 === 1) return 0; let dp = Array.from(new Array(n + 1), () => new Array(total / 2 + 1).fill(0)); for (let i = 0; i = 0) { dp..
