5557번 1학년 (자바스크립트)

문제

상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다.

상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 예를 들어, "8+3+2-4-8-7+2+4+0+8=8"은 올바른 등식이지만, 8+3+2-4-8-7이 음수이기 때문에, 상근이가 만들 수 없는 등식이다.

숫자가 주어졌을 때, 상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 숫자의 개수 N이 주어진다. (3 ≤ N ≤ 100) 둘째 줄에는 0 이상 9 이하의 정수 N개가 공백으로 구분해 주어진다.

출력

첫째 줄에 상근이가 만들 수 있는 올바른 등식의 개수를 출력한다. 이 값은 263-1 이하이다.

====

문제 분석

인덱스 처음부터 마지막 직전(n-1)까지 + - 를 사용해가면서 arr의 마지막 값을 만드는 경우의 수를 출력하는 방식이다.

이 때 계산으로 나온 숫자는 0이상 20이하라는 제한이 있지만, DFS나 BFS와 같은 완전 탐색으로 계산을 할 경우 최대 

2^100 의 연산이 일어 날 수 있어서 특정 규칙을 찾아야했다.

0~20이라는 조건이라는 특이점을 사용하여 각 인덱스별로 0부터 20을 만들 수 있는 경우의 수를 기록하는 것이다.

예를 들어 인덱스 0 이 8일 때, 인덱스 0으로 만들 수 있는 수는 8 1개이다.

인덱스 1이 3일 때, 만들 수 있는 수는 이전 인덱스 0까지 만들 수 있는 경우의 수들로 조합을 만드는 것이다.

인덱스 0까지 만들 수 있는 것은 8 하나였다.

그렇다면 이제 인덱스 1인 3을 이용하여 나올 수 있는 경우의 수는 5 (8-3), 11(8+3) 이렇게 두개이다.

이후 인덱스 2인 15 라면 만들 수 있는 것은 이전까지 만들 수 있던 5와 11을 사용하여

20( 5+15), -10(5-15), 26(11+15), -4(11-15) 이다.

여기에서 0이상 20이하인 수는 20이다.

즉. 각 인덱스까지 사용할 수 있는 경우의 수로 그 다음 인덱스에서 현재 arr의 값을 덧셈 또는 뺄셈을 하여 나온 결과를 dp에 계속 기록해야나가는 것이다.

for (let i = 1; i < n - 1; i++) {
        const currentValue = arr[i];
        for (let j = 0; j <= 20; j++) {
            if (dp[i - 1][j] !== 0) {
                const plus = j + currentValue;
                const minus = j - currentValue;
                if (plus <= 20) {
                    dp[i][plus] += BigInt(dp[i - 1][j]);
                }
                if (minus >= 0) {
                    dp[i][minus] += BigInt(dp[i - 1][j]);
                }
            }
        }
    }

주의할 점은, 출력에 나온 조건인 '만들 수 있는 올바른 등식의 개수를 출력한다. 이 값은 263-1 이하이다.' 을 활용하여 각 인덱스를 BigInt로 기록해야한다는 것이다.

정답 코드

const main = (n, arr) => {
    const dp = Array.from({ length: n - 1 }, () =>
        Array.from({ length: 21 }, () => BigInt(0))
    );
    const answer = arr[arr.length - 1];
    dp[0][arr[0]] = BigInt(1);

    for (let i = 1; i < n - 1; i++) {
        const currentValue = arr[i];
        for (let j = 0; j <= 20; j++) {
            if (dp[i - 1][j] !== 0) {
                const plus = j + currentValue;
                const minus = j - currentValue;
                if (plus <= 20) {
                    dp[i][plus] += BigInt(dp[i - 1][j]);
                }
                if (minus >= 0) {
                    dp[i][minus] += BigInt(dp[i - 1][j]);
                }
            }
        }
    }
    console.log(dp[n - 2][answer].toString());
};

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const n = +input[0];
const arr = input[1].split(' ').map((v) => +v);
main(n, arr);