DP

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..

https://www.acmicpc.net/problem/16173코드const fs = require("fs");const filePath = process.platform === "linux" ? "dev/stdin" : "./input.txt";const [n, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n");board = arr.map((row) => { return row .trim() .split(" ") .map((item) => +item);});function solution(n, board) { let dp = Array.from(new Array(n), () => new Array(n).fill(..

요구사항 정리아이들의 이동을 최소로 하여 아이들의 번호가 오름차순으로 정렬되도록 만들자.예를 들자면, 3 7 5 2 6 1 4와 같이 아이들이 일렬로 서있다고 할 때, 이것을 최소한의 이동만으로 1 2 3 4 5 6 7로 만들어주면 된다.입력첫째줄 : 아이들의 수 N (2 ≤ N ≤ 200, N은 정수)둘째줄~ : 1~N까지의 숫자가 한 줄에 하나씩 주어짐출력아이들을 번호 오름차순으로 정렬하기 위해 최소한으로 옮기는 횟수 출력.코드n = int(input())arr = [int(input()) for _ in range(n)]# LISdp = [1]*nfor i in range(n): for j in range(i): if arr[i] > arr[j]: dp[i] =..

https://www.acmicpc.net/problem/10164코드n, m, k = map(int, input().split())def find_path(r, c): # 세로 길이가 r, 가로 길이가 c인 격자에서 경로의 개수 구하기 dp = [[0]*(c) for _ in range(r)] dp[0][0] = 1 for i in range(r): for j in range(c): if i+1  풀이목적지까지 경로의 개수 구하는데 중간에 꼭 경유해야 하는 곳이 있다면 다음과 같이 출발지-경유지까지 가는 길과 경유지-목적지까지 가는 길의 경로의 수를 각각 구해서 곱하면 된다.1번이 출발지, 15번이 목적지, 8번이 경유지라면 (1번에서 8번까지 가는..

https://www.acmicpc.net/problem/17212 코드n = int(input())dp = [int(1e9)]*(n+1) # dp[i]: i원 만드는 데 필요한 동전의 최소 개수dp[0] = 0for i in range(1, n+1): for j in [1, 2, 5, 7]: if i-j