목록알고리즘/DP (6)

개발새발 로그

[JS] 백준 1149 - RGB거리 - DP

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 📋풀이방법 1. 주어진 빨강, 초록, 파랑의 값을 아래의 점화식으로 처리한다. dp[n][0] = min(dp[n-1][1], dp[n-1][2]) + rgb[n][0] dp[n][1] = min(dp[n-1][0], dp[n-1][2]) + rgb[n][1] dp[n][2] = min(dp[n-1][0], dp[n-1][1]) + rgb[n][2] - dp배열안에 각각의 색..
알고리즘/DP 2023. 9. 7. 01:23
[JS] 백준 9059 : 1, 2, 3 더하기 - DP

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 📋풀이방법 1. 1과 2와 3으로 만드는 것이므로 일단 1, 2, 3의 숫자를 만들 수 있는 경우의 수를 수동으로 세본다. 2. 그럼 아래와 같이 나오게 된다. 3. 이후의 숫자를 다시 수동으로 적으면서 찾아보자 4. 이때 규칙이 생기는데 이전에 구했던 1, 2, 3 의 경우의 수를 이용할 수 있게 된다. 🤟내 제출 var fs = require('fs'); var inputs = fs.readFileSync('/dev/stdin').toString().split('\n').map(v=>Numb..
알고리즘/DP 2023. 8. 29. 00:39
[JS] 백준 11054번 : 가자 긴 바이토닉 부분 수열 - DP(다이나믹 프로그래밍)

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이방법 1. N크기의 배열에 현재 숫자가 뒤에서 가장 큰 숫자일 때의 가장 긴 바이토닉 부분 수열 중 갯수가 가장 큰 값을 넣는다 2. N크기의 배열에 현재 숫자가 앞에서 가장 큰 숫자일 때의 가장 긴 바이토닉 부분 수열 중 갯수가 가장 큰 값을 넣는다. 3. 두 배열을 구했으면 두 배열의 값들을 인덱스에 대응되는 값끼리 더하고 -1을 한다(자신 숫자가 겹치므로 -1로 제외) 4. 두 배열을 더하는 것은 가운데 숫..
알고리즘/DP 2023. 8. 4. 01:04
[JS] 백준 2293번 : 동전 1 - DP (백준 메모리초과)

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 📋풀이방법 1. 손으로 풀 수 있을 때까지 문제를 나열해보자 2. 이때 규칙을 찾아야한다. 3. 그림을 봤을 때 1원만 사용했을 때와 1원과 2원을 사용했을 때의 차이가 있다. 4. 차이에서 규칙을 찾아야한다. 5. 이때 중요한 점은 0원일 때의 경우의 수도 넣어야한다. ->0원을 만드는 경우의 수는 0개의 동전을 선택하는 방법이므로 1가지입니다. 🤟내 제출 const fs = require("fs..
알고리즘/DP 2023. 8. 2. 01:55
[JS] 백준 9251번 : LCS - DP문제

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS 참고 https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Comm..
알고리즘/DP 2023. 7. 29. 02:43
[JS] 백준 12865 : 평범한 배낭 - DP문제

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 📋풀이방법 1. 첫번째 물건(무게 : 6, 가치 : 13)을 dp배열에 넣어서 검사한다. 2. 두번째 물건(무게 : 4, 가치: 8)을 넣어 검사해본다. 3. 세번째 물거(무게 : 3, 가치 : 6) 4. 이를 반복해준다. 🤟내 제출 const fs = require("fs"); const filePath = process.plat..
알고리즘/DP 2023. 7. 26. 02:52
이전 Prev 1 Next 다음