[JavaScript/DP] 백준 실버 3 : 14501 - 퇴사

https://www.acmicpc.net/problem/14501

14501번: 퇴사

---

📌 작성한 코드 (1번의 풀이) 

//14501

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const n = parseInt(input.shift());
const arr = input.map((i) => i.split(" ").map(Number));

const resign = () => {
    const dp = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        const [t, p] = arr[i];
        if (i + t <= n) {
            // i번째 날에 일을 했으면
            dp[i + t] = Math.max(dp[i + t], dp[i] + p);
        }
        // i번째 날에 일을 하지 않았으면
        dp[i + 1] = Math.max(dp[i], dp[i + 1]);
    }

    return Math.max(...dp);
};

console.log(resign());

 

 

 

📌 참고한 블로그 

https://velog.io/@skyepodium/%EB%B0%B1%EC%A4%80-14501-%ED%87%B4%EC%82%AC-exjyfr5vgj

백준 14501 퇴사

---

 

📌 풀이 방법 

DP(동적계획법) 사용해서 문제 풀이 

- DP 테이블에는 해당 날짜에 받을 수 있는 금액의 최댓값을 저장할 것이다.

- 예 ) [0,0,0,10, ...] 

 

📍 점화식

 

받을 수 있는 돈의 최댓값을 구하기 위해서 계산해 볼 때 고려해야 할 상황은 2가지이다.

(1) 그 날에 일을 한 경우 

(2) 그 날에 일을 하지 않은 경우 

-> 어떤 행동이 더 돈을 많이 받을지 모르기 때문에 둘을 계산해서 돈을 더 많이 받는 날이 dp에 저장되도록 해야한다. 

 

✅ 1. O(N)

(1) 일 한 경우

일하는 날로부터 상담 일수만큼 시간이 지나면 돈을 받을 수 있다. 

-> 그렇다면 i번째 날 일을 했다면 i + T[i]의 날에 돈을 받을 수 있다. 

-> 우리는 n+1일에 퇴사할 것이기 때문에, 받을 수 있는 날짜가 n+1 보다 작거나 같은 날의 돈만 받을 수 있다.

 

i+ t[i] 날에 받을 수 있는 돈

= i번째 날에 받을 수 있는 돈(dp[i]) + i번째 날에 일하면 최종적으로 받을 수 있는 돈 (p[i])

if (i + t[i] <= n) {
     dp[i + t[i]] = Math.max(dp[i + t[i]], dp[i] + p[i]);
}

 

(2) 일하지 않은 경우 

일하지 않은 경우는 그 전날에 받을 수 있는 값에서 어떤 행동도 하지 않았기 때문에

현재까지 저장된 최댓값과 전날에 받을 수 있는 최댓값을 비교해서 업데이트 해준다.

dp[i + 1] = Math.max(dp[i], dp[i + 1]);

 

* 점화식과 작성한 코드가 다르게 보일 수 있는데,

점화식에서는 첫번째 날을 1일로 잡아서 조건도 n+1로 설정하고 반복문도 1부터 n까지로 두고 푼것이고,

코드에서는 배열 인덱스가 0부터 시작해서 0을 1일로 설정하고 풀어서 0부터 n-1까지 반복하고, 제한 조건도 n으로 두었다. 

 

 

---

 

✅ 2. O(N^2)

(1) 일 한 경우 

- 4일에 받을 수 있는 돈의 경우의 수를 살펴보면 

(1) 1일에 일하고, 4일에 돈 받기

(2) 3일에 일하고, 4일에 돈 받기 

(3) 일 안하고, 0원 받기 

 // (4) 2일에 일하면, 4일에 돈 못받음 (x)

-> 이렇게 (해당 날짜 + 상담 일수)가 현재 날짜 보다 작거나 같은 날에 일한 돈은 받을 수 있고, 더 큰 날에는 돈을 받을 수 없다.

 

(i는 일한 날짜, j는 구하려고 하는 날짜보다 이전의 날짜들 인덱스)

-> j번째 날에서 t[j]만큼 일을 하고 보상 p[j]를 i번째 날에 받은 경우

-> 이때 해당 날짜 = j , 상담 일수 = t[j], 받을 수 있는 돈 = p[j]

 

if(j + t[j] == i){
      d[i] = Math.max(dp[i], dp[j] + p[j]);
}

 

(2) 일하지 않은 경우 

위와 마찬가지로 이전값과 비교하기 

여기에서는 전 날이 아니라 비교하고 있는 j번째 날과 비교해주면 된다.

d[i] = max(d[i], d[j]);

 

 

 

📌 사담 

- 이해를 쉽게 하기 위해서 2번째 풀이도 넣어보았다 

- 효율적인 면이나 보기 좋은 코드는 1번 풀이라고 생각한다.

- dp문제는 점화식을 세우기가 어려운 것 같다. 

  다른 분들의 풀이를 보고 식 세우는 법을 배워가면서 점화식 세우는 사고를 배우려고 노력하고 있다.

---