Softeer [Level 3] [한양대 HCPC 2023] Hanyang Popularity Exceeding Competition {언어 : JavaScript}

문제 링크

https://softeer.ai/practice/9495

Softeer - 현대자동차그룹 SW인재확보플랫폼

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
const inputData = [];

rl.on('line', (line) => {
    inputData.push(line.split(" ").map((e) => Number(e)));
}).on('close', () => {
    const n = inputData[0];
    const celebrities = inputData.slice(1);
    // dp를 2차원 배열로 생각할 것
    const dp = Array.from({length: n}, () => [0, 0]);
    // dp[0]은 방문 했을 때, dp[1]은 현재 지점을 방문하지 않았을 때,
    dp[0][0] = celebrities[0][0] <= celebrities[0][1] ? 1 : 0;
    for (let i = 1; i < n; i++) {
        const [pi, ci] = celebrities[i];
        // 현재 철민이의 인기도
        const [xi0, xi1] = dp[i-1];
        const xni0 = Math.abs(pi-xi0) <= ci ? xi0+1 : xi0;
        const xni1 = Math.abs(pi-xi1) <= ci ? xi1+1 : xi1;

        dp[i][0] = Math.max(xni0, xni1);
        dp[i][1] = Math.max(xi0, xi1);
    }
    console.log(Math.max(...dp[n-1]));
    process.exit(0);
});

풀이 방법

1. 동적계획법을 사용할 예정이다.
2. dp를 2차원 배열로 만들고 dp[i]의 0번째 인덱스는 방문한 경우, 1번째 인덱스는 방문하지 않은 경우로 나눈다.
3. dp[1]을 먼저 설정해준다.
   1. 처음 인기도는 0이므로 인기도가 첫 번째 유명인의 인기도와 친화력에 달려있다.
4. dp[i]는 다음과 같다.
   1. 이전의 dp[i-1]에서 celebritys[i-1] 즉, i-1 번째 유명인을 방문 했을 때와 방문하지 않았을 때의 인기도가 현재의 인기도가 된다.
   2. 현재의 인기도 xi0와 xi1로 현재 유명인을 만났을 때 오르는지 각각 구하고 최대값을 dp[i][0]에 치환한다.
   3. dp[i][1]은 현재 유명인을 만나지 않을 것이므로 xi0와 xi1 중 큰 값으로 치환한다.
5. 마지막으로 dp[n-1]중 최대값을 출력하면 끝!

느낀점

• 아직 동적계획법에 대해 잘 모르는 경우 다음과 같은 실수를 할 수 있다.

const answer = celebrities.reduce((x, [pi, ci]) => {
    if (Math.abs(pi-x) <= ci) {
        return x+1;
    }
    return x;
}, 0);
console.log(answer);

• 그냥 배열만 보고 계속해서 더해 나가면 되는거 아닌가? 하는 실수이다.
• 이렇게 해도 테스트케이스 1, 2, 3을 맞출 수 있지만 이대로 제출하면 바로 틀린다.
• 따라서 경우의 수를 모두 생각하고 문제를 풀어야 한다.
• 또한 문제 안의 힌트를 찾는 것 또한 중요하다.
  • 힌트는
    • 유명인을 건너 뛸 수 있다.
    • 유명인을 마주해도 인기도가 오르지 않을 수 있다.
  • 이 힌트를 보고 모두 방문 하지 않고 건너 뛰는 방법을 구상해야 한다.