[백준] 1823 수확 (Javascript)

잭슨·2024년 3월 25일

DP 다이나믹 프로그래밍 백준 알고리즘 자바스크립트

알고리즘 문제 풀이

목록 보기

61/130

문제

BOJ1823_수확

풀이

오답 (투 포인터)

가치가 큰 벼를 나중에 수확할수록 이익은 커진다. 따라서 투 포인터를 이용해 아래와 같이 작성했다.

맨 앞의 벼(front)와 맨 뒤의 벼(rear)의 가치를 비교하여 가치가 더 낮은 벼를 먼저 수확하고, 만약 가치가 같다면 front+1 과 rear-1 번째 벼를 비교하여 최대이익을 구할 수 있을 거라고 생각했다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const arr = input.slice(1).map(Number);

// 반복을 한 번 수행할 때마다 첫 번째 벼나 마지막 벼만 수확할 수 있다.
// 가치가 큰 벼를 나중에 수확할수록 이익이 커진다.

let answer = 0;
let i = 1;
let front = 0;
let rear = N - 1;
while (front <= rear) {
    if (arr[front] < arr[rear]) {
        answer += arr[front++] * i++;
    } else if (arr[front] > arr[rear]) {
        answer += arr[rear--] * i++;
    } else {
        let innerFront = front + 1;
        let innerRear = rear - 1;
        let isChanged = false;
        while (innerFront <= innerRear) {
            if (arr[innerFront] < arr[innerRear]) {
                answer += arr[front++] * i++;
                isChanged = true;
                break;
            } else if (arr[innerFront] > arr[innerRear]) {
                answer += arr[rear--] * i++;
                isChanged = true;
                break;
            } else {
                innerFront++;
                innerRear--;
            }
        }
        if (!isChanged) {
            answer += arr[front++] * i++;
        }
    }
}

console.log(answer);

하지만 입력이 7 5 2 1 8 처럼 주어졌을 때는 7+5 가 1+8 보다 크므로 더 8과 1을 먼저 수확해야 최대의 이익을 얻을 수 있지만 위와 같이 코드를 작성할 경우 7과 8을 비교할 때 7이 더 작으므로 7을 먼저 수확하기 때문에 오답이 나온다.

정답 (DP)

결국에는 모든 조합을 확인해야 하는 문제이다. 조합을 그대로 사용하면 시간초과가 나기 때문에 2차원 배열의 메모이제이션 기법을 이용해서 풀어야 한다.

점화식은 아래와 같이 세울 수 있다.
dp[left][right] = max(DP(left+1, right, count+1) + arr[left][right] * count, DP(left, right-1, count+1 + arr[left][right] * count))

이 점화식을 이용하면 dp[left][right] 에는 첫 번째 부터 left 번째 까지의 벼와, 마지막부터 right 번째 까지의 벼를 수확했을 때 얻을 수 있는 최대 이익이 저장된다.

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const arr = input.slice(1).map(Number);
const dp = Array.from({ length: N }, () => Array(N).fill(0));

const getDP = (left, right, count) => {
    if (left > right) return 0;
    if (dp[left][right] !== 0) return dp[left][right];

    const leftSum = getDP(left + 1, right, count + 1) + arr[left] * count;
    const rightSum = getDP(left, right - 1, count + 1) + arr[right] * count;

    dp[left][right] = Math.max(leftSum, rightSum);
    return dp[left][right];
};

let answer = getDP(0, N - 1, 1);
console.log(answer);