Softeer [Level 3] 나무 수확 {언어 : JavaScript} [다시 풀어 보기]

문제 링크

https://softeer.ai/practice/7369

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][0];
    const field = inputData.slice(1);

    const noSpring = Array.from({length: n}, () => Array(n).fill(0));
    const yesSpring = Array.from({length: n}, () => Array(n).fill(0));
    noSpring[0][0] = field[0][0];
    yesSpring[0][0] = field[0][0]*2;
    
    
    // 가로 세로 채우기
    for (let i = 1; i < n; i++) {
        noSpring[0][i] = field[0][i] + noSpring[0][i-1];
        noSpring[i][0] = field[i][0] + noSpring[i-1][0];
        yesSpring[0][i] = field[0][i] + Math.max(yesSpring[0][i-1], noSpring[0][i-1] + field[0][i]);
        yesSpring[i][0] = field[i][0] + Math.max(yesSpring[i-1][0], noSpring[i-1][0] + field[i][0]);
    }
    

    for (let i = 1; i < n; i++) {
        for (let j = 1; j < n; j++) {
            noSpring[i][j] = field[i][j] + Math.max(noSpring[i-1][j], noSpring[i][j-1]);
            yesSpring[i][j] = field[i][j] + Math.max(Math.max(yesSpring[i-1][j], yesSpring[i][j-1]), Math.max(noSpring[i-1][j], noSpring[i][j-1])+field[i][j]);
        }
    }
    console.log(yesSpring[n-1][n-1]);
    process.exit(0);
});

풀이 방법

 

1. 초기화
   inputData 배열에 입력 데이터를 저장한 후, noSpring과 yesSpring이라는 두 개의 2차원 배열을 사용한다.
   • noSpring[i][j]는 특정 칸 (i, j)까지 수로를 설치했을 때, 스프링클러 없이 얻을 수 있는 최대 열매 수확량을 저장한다.
   • yesSpring[i][j]는 (i, j)까지 수로를 설치하고 스프링클러를 설치했을 때 얻을 수 있는 최대 열매 수확량을 저장한다.
2. 첫 번째 행과 첫 번째 열 계산
   먼저, 첫 번째 행과 첫 번째 열의 각 칸까지의 수확량을 계산한다.
   • noSpring[0][i]와 noSpring[i][0]은 수로만 설치했을 때의 열매 수확량을 계산한다.
   • yesSpring[0][i]와 yesSpring[i][0]은 수로에 스프링클러를 설치했을 때의 열매 수확량을 계산한다.
3. 동적 계획법을 이용한 나머지 칸 계산
   이후 모든 칸을 순차적으로 탐색하면서 (i, j)까지의 수확량을 계산한다.
   • noSpring[i][j]은 (i, j)까지 수로만 설치했을 때의 최대 수확량으로, 위쪽 칸이나 왼쪽 칸에서 온 수확량 중 큰 값에 현재 칸의 수확량을 더한다.
   • yesSpring[i][j]은 (i, j)까지 스프링클러가 포함된 최대 수확량으로, 이전 경로 중 스프링클러가 있는 경로와 없는 경로의 값들을 고려하여 최대값을 구한. 이를 통해 스프링클러를 놓았을 때의 2배 수확량을 최대로 계산한다.
4. 결과 출력
   최종적으로 yesSpring[n-1][n-1]에 저장된 값이 (n, n)까지 수로와 스프링클러를 설치하여 얻을 수 있는 최대 열매 수확량이므로 출력하면 끝!

 

느낀점

• DP로 풀어야겠다고 생각은 했으나 3차원 dp와 bfs를 접목시켜야 한다고 생각했다.
• 하지만 단순하게 dp를 2개 사용하여 스프링 쿨러를 설치 전과 후로 나눠서 최대값을 찾으면 되는 문제였다.

틀린 코드

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][0];
    const isValid = (nr, nc) => {
        return 0 <= nr && nr < n && 0 <= nc && nc < n;
    }
    const dr = [1, 0];
    const dc = [0, 1];
    
    const field = inputData.slice(1);
    const dp = Array.from({length: n}, () => Array.from({length: n}, () => [0, 0]));
    dp[0][0][0] = field[0][0] * 2;
    dp[0][0][1] = field[0][0];
    const dq = [[0, 0]];
    while (dq.length) {
        const [r, c] = dq.shift();
        for (let d = 0; d < 2; d++) {
            const nr = r + dr[d];
            const nc = c + dc[d];
            if (isValid(nr, nc)) {
                const maxV = Math.max(dp[r][c][1], field[nr][nc]);
                const newScore = dp[r][c][0] - dp[r][c][1] + maxV + field[nr][nc];
                if (dp[nr][nc][0] === 0 || dp[nr][nc][0] < newScore || (dp[nr][nc][0] === newScore && dp[r][c][1] > maxV)) {
                    dp[nr][nc][0] = newScore;
                    dp[nr][nc][1] = maxV;
                    dq.push([nr, nc]);
                }
            }
        }
    }
    console.log(dp[n-1][n-1][0]);
    process.exit(0);
});

• dp[i][j][1]에 현 위치에 최대값을 넣었지만 문제는 지금까지 지나온 경로에 최대값과 일치하지 않을 수 있다는 오류를 범했다.