dynamicProgramming

[백준 1520 - Node.js] 내리막길

🔗 문제 링크 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net ✏️ 풀이 const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); const [M, N] = input.shift().split(' ').map(Number); const map = input.map(v => v.split(' ').map(Number)); const offset = ..

[백준 2294] 동전 2 with Python

문제 링크 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 풀이 import sys n, k = map(int, sys.stdin.readline().split()) coin = [int(sys.stdin.readline()) for _ in range(n)] dp = [10001 for _ in range(k+1)] dp[0] = 0 for i in range(1, k+1): for j in coin: if i ..

[백준 2293] 동전 1 with Python

문제 링크 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 import sys n, k = map(int, sys.stdin.readline().split()) coin = [int(sys.stdin.readline()) for _ in range(n)] dp = [1]+[0]*k for value in coin: for i in range(1, k+1): if i < value: continue dp[i] += dp[i-value] pri..

[백준 11057] 오르막 수 with Python

문제 링크 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 풀이 N = int(input()) dp = [[0]*10 for _ in range(N+1)] dp[1] = [1]*10 for i in range(2, N+1): for j in range(10): dp[i][j] += sum([dp[i-1][k] for k in range(j+1)]) print(sum(dp[N])%10007) dp[N]은 N자리..

[백준 9251] LCS with Python

문제 링크 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 X = input() Y = input() LCS = [[0]*(len(Y)+1) for _ in range(len(X)+1)] for i in range(1, len(X)+1): for j in range(1, len(Y)+1): if X[i-1] == Y[j-1]: LCS[i][j] = LCS[i-1][j-1] + 1 else: LC..

[백준 10844] 쉬운 계단 수 with Python

문제 링크 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 N = int(input()) dp = [[0]*10 for _ in range(N+1)] dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] for i in range(2, N+1): for j in range(10): if j == 0: dp[i][0] = dp[i-1][1] elif j == 9: dp[i][9] = dp[i-1][8] else: dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] print(sum(dp[N])%1000000000) 길이가..

[백준 17626] Four Squares with Node.js

문제 링크 https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 풀이 const solve = n => { const dp = new Array(n+1).fill(0); dp[1] = 1; for (let i=2; i

[백준 11052] 카드 구매하기 with Python

문제 링크 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 import sys N = int(sys.stdin.readline()) card = [0] + list(map(int, sys.stdin.readline().split())) dp = [0]*(N+1) dp[1] = card[1] for i in range(2, N+1): highest = 0 for j in range(1, i//2 + 1): if dp[j] + dp[i-j] > hi..

[백준 1149] RGB거리 with Node.js

문제 링크 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 const solve = (n, rgb) => { dp = [...new Array(n+1)].map(v => new Array(3).fill(0)); dp[1] = rgb[0]; for (let i=2; i cost.split(' ').map(v => +v))); dp[n][0]을 n번째 집을 빨간색으로 칠했을 때 전체 비용의 최솟값, dp[n][1]을 n번..

[백준 2156] 포도주 시식 with Node.js

문제 링크 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 const solve = (n, wine) => { if (n === 1) return wine[0]; else if (n === 2) return wine[0] + wine[1]; const dp = new Array(n).fill(0); dp[1] = wine[0]; dp[2] = wine[0] + wine[1]; for (let i=3; i +v); console.log(sol..