문제 이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩 니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.) 풀이 function solution(n, arr) { // dy[i]는 i분 안에 풀 수 있는 최대 점수 // 해당 문제를 풀 것인지, 아닌지에 따라 최대 점수 구하기 const dy = Array.from({ length: n + 1 }).fill(0); for (let i = 0; i < arr.length; i++) { const [ps, pt] =..
문제 철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다. 그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가? 풀이 /** * 다이나믹 프로그래밍(동적 계획법) * - 점화식(관계식)을 만드는 것이 중요 * - 문제를 작은 단위로 쪼개서 구하고, 이걸 기록해뒀다가 문제 범위(데이터 범위) 넓히기 * - dy[n] = dy[n-1] + 3처럼 관계를 구한다. * - 많은 문제를 풀어봐야 한다. */ function solution(n) { const dy = Array.from({ length: n + 1 }).fill(0); dy[1] = 1; dy..
문제 다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환 해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다. 풀이 function solution(m, coin) { let dy = Array.from({ length: m + 1 }, () => 1000); // 가장 작은 동전으로 금액 m 만들 때보다 크게 설정 dy[0] = 0; // 각 동전을 사용할 경우 for (let i = 0; i < coin.length; i++) { // 해당 동전 사용 시 금액마다 필요한 동전 개수 세기 for (let j = coin[i]; j
문제 https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 풀이 const fs = require("fs"); const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; let N = +fs.readFileSync(filePath).toString().trim(); const dp = Array.from({ length: N + 1 }..
