[백준] 14501번: 퇴사 자바스크립트

알고리즘별 풀기-> 브루트포스 알고리즘에서 14501문제를 만났다.

알고리즘이 브루트포스 알고리즘이여서 완전탐색과 백트래킹, 재귀를 생각하며 문제를 품
하지만 푸면 풀수록 조건들이 까다로워져서 구글링을 해봤더니 대부분이 dp를 활용해서 품
dp는 큰 문제를 작은 문제로 나누고 그 작은 문제의 답이 중복되고 재사용되는 경우에 사용함

문제

let n = +input.shift()
let arr = input.map(v=>v.split(' ').map(Number))

n을 7로 두고
뒤에 나오는 7줄의 값을 배열로 저장
[ [ 3, 10 ],[ 5, 20 ],[ 1, 10 ],[ 1, 20 ],[ 2, 15 ],[ 4, 40 ],[ 1, 200 ] ]

dp를 활용하기 위해 길이가 n인 빈 배열 dp를 생성

과정

for문을 돌면서 dp에 돈을 채워넣음
만약 a일부터 b일동안 일했는데 a+b가 n을 넘어가는 경우는 넘어감

1. 1일날에 일하면 벌리는 돈을 dp[0]에 ++하고, 1일날부터 3일동안 일을 한 뒤 4~7일날에 벌려있는 돈을 dp[0]와 비교 후 더 큰 경우 업데이트(1일째여서 dp에는 다 0이 들어가있음)
   dp => 10,0,0,10,10,10,10
2. 2일날에 일하면 벌리는 돈을 dp[1]에 ++하고, 2일날부터 5일동안 일을 한 뒤인 7일날에 벌려있는 돈을 dp[1]와 비교 후 더 큰 경 우 업데이트
   dp => 10,20,0,10,10,10,20
3. 3일날에 일하면 벌리는 돈을 dp[2]에 ++하고, 3일날부터 1일동안 일을 한 뒤인 4~7일날에 벌려있는 돈을 dp[2]와 비교 후 더 큰 경우 업데이트
   dp => 10,20,10,10,10,10,20
4. 4일날에 일하면 벌리는 돈을 dp[3]에 ++하고, 4일날부터 1일동안 일을한 뒤인 5~7일날에 벌려있는 돈을 dp[3]와 비교 후 더 큰 경우 업데이트
   dp => 10,20,10,30,30,30,30
5. 5일날에 일하면 벌리는 돈을 dp[4]에 ++하고, 5일날부터 2일동안 일을한 뒤인 7일날에 벌려있는 돈을 dp[4]와 비교 후 더 큰 경우 업데이트
   dp => 10,20,10,30,45,30,45
6. 6일날에 일하면 돈을 받는 날인 10일 후가 이미 퇴사하고 난뒤인 7일 밖이기 때문에 넘어감
   dp => 10,20,10,30,45,30,45
7. 7일날에 일하면 돈을 받는 날인 9일 후가 이미 퇴사하고 난뒤인 7일 밖이기 때문에 넘어감
   dp => 10,20,10,30,45,30,45

코드

const fs = require('fs');
const input = fs.readFileSync('../text.txt').toString().split('\n');
let n = +input.shift()
let arr = input.map(v=>v.split(' ').map(Number))
const dp = new Array(n).fill(0)

for (let i = 0; i < n; i++) { // 0일~6일
    console.log("for문 돌고 dp",dp)
    const [duration, profit] = arr[i];
    console.log("i+duration",i+duration,n)
    if (i + duration > n){
        console.log("넘어감")
        continue
    } 
    dp[i] += profit;
    console.log("dp",dp);
    for (let j = i + duration; j < n; j++) {
        console.log("i,j",i,j)
        console.log("--, j",j,dp[i], dp[j]);
        dp[j] = Math.max(dp[j], dp[i]);
        console.log("after",dp[j])
    }
}
console.log(Math.max(...dp));

🫠

코드 출처: https://breathtaking-life.tistory.com/149