2632 피자 판매 (자바스크립트)

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

고객이 두 종류의 피자 A와 B를 취급하는 피자가게에서 피자를 주문하고자 한다. <그림 1>과 같이 각 종류의 피자는 다양한 크기의 여러 개의 피자조각으로 나누어져 있다. 각 조각에 쓰여진 숫자는 피자조각의 크기를 나타낸다.

고객이 원하는 피자의 크기를 이야기하면, 피자가게에서는 한 종류의 피자를 2 조각 이상 판매할 때는 반드시 연속된 조각들을 잘라서 판매한다. 이때 판매한 피자조각의 크기 합이 주문한 크기가 되어야 한다. 판매한 피자조각은 모두 A종류이거나, 모두 B종류이거나, 또는 A와 B 종류가 혼합될 수 있다. 예를 들어서, <그림 1> 과 같이 잘라진 피자가 있을 때, 손님이 전체 크기가 7 인 피자를 주문하면, 피자 가게에서는 <그림2>와 같이 5 가지 방법으로 피자를 판매할 수 있다.

피자가게에서 손님이 원하는 크기의 피자를 판매하는 모든 방법의 가지 수를 계산하는 프로그램을 작성하시오

입력

첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n ≤ 1000). 세 번째 줄부터 차례로 m 개의 줄에는 피자 A의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 그 다음 n 개의 줄에는 차례로 피자B의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 각 종류의 피자조각의 크기는 시계방향으로 차례로 주어지며, 각 피자 조각의 크기는 1000 이하의 자연수이다.

출력

첫째 줄에는 피자를 판매하는 방법의 가지 수를 나타내는 정수를 출력한다. 피자를 판매하는 방법이 없는 경우에는 숫자 0을 출력한다.

 

=====

문제 풀이

두개의 피자를 활용하거나 하나의 피자에서 합이 target 이 되면 answer를 +1 해주면 된다.

우선 각각의 피자에서 범위 내의 피자 합을 구한다.

0부터 2*n -1 길이의 누적합을 구하고  그 누적합을 통해 범위 내 합을 구하는 로직을 짠다.

const makeSum = (arr) => {
    const n = arr.length;
    const sums = [arr[0]];

    for (let i = 1; i < n * 2 - 1; i++) {
        sums[i] = sums[i - 1] + arr[i % n];
    }

};

i~j의 의 범위 합은 sums[j]- sums[i-1] 이 된다. 

원형인 것을 감안하면 인덱스 4부터 출발하여 인덱스 2까지의 합은 sums[2+len/2] -sums[4] 가 된다.

이것을 프로토타입으로 메서드 추가함.

Array.prototype.sliceSum = function (start, end) {
    if (start === 0) return this[end];
    if (start > end) {
        const N = Math.ceil(this.length / 2);

        return this[end + N] - this[start - 1];
    }
    return this[end] - this[start - 1];
};

위 메서드를 통해 범위의 합을 구한다. 

let answer = 0;
const makeSum = (arr) => {
    const n = arr.length;
    const sums = [arr[0]];

    for (let i = 1; i < n * 2 - 1; i++) {
        sums[i] = sums[i - 1] + arr[i % n];
    }
    const result = [];
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (j === i - 1) continue; //여기를 점프하는 이유는 전체 배열의 합이므로 중복을 위해 패스함
            const value = sums.sliceSum(i, j);
            if (value < target) {
                result.push(value);
                continue;
            }
            if (value === target) {
                answer++;	// 이 피자 하나만으로 target을 만드는거니 패스
            }
        }
    }

    return result;
};

위의 함수를 통해 각 배열의 범위 합들을 구하고 그 두개의 합 배열을 통해 target이 되는 것을 찾으면 됨.

중복인 경우도 있으니 각 배열 요소의 cnt를 구하고 두 배열에서 끄집어 낸 수의 합이 target이 되면 

cnt[a] * cnt[b] 를 answer에 더해줌

const arrSums = makeSum(arr);
const brrSums = makeSum(brr);

arrSums.sort((a, b) => a - b);

const aCnt = arrSums.reduce((acc, cur) => {
    acc[cur] = (acc[cur] || 0) + 1;
    return acc;
}, {});
const bCnt = brrSums.reduce((acc, cur) => {
    acc[cur] = (acc[cur] || 0) + 1;
    return acc;
}, {});

const a = [...new Set(arrSums)];
const b = [...new Set(brrSums)];

for (const v of b) {
    let s = 0;
    let e = a.length - 1;
    while (s <= e) {
        const mid = Math.floor((s + e) / 2);
        const valueArr = a[mid];
        const total = valueArr + v;
        if (total === target) {
            answer += aCnt[valueArr] * bCnt[v];
            break;
        }
        if (total > target) {
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }
}

console.log(answer);

전체 코드

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

const target = +input[0];
const [m, n] = input[1].split(' ').map(Number);
const arr = input.slice(2, m + 2).map(Number);
const brr = input.slice(m + 2).map(Number);

Array.prototype.sliceSum = function (start, end) {
    if (start === 0) return this[end];
    if (start > end) {
        const N = Math.ceil(this.length / 2);

        return this[end + N] - this[start - 1];
    }
    return this[end] - this[start - 1];
};

let answer = 0;
const makeSum = (arr) => {
    const n = arr.length;
    const sums = [arr[0]];

    for (let i = 1; i < n * 2 - 1; i++) {
        sums[i] = sums[i - 1] + arr[i % n];
    }
    const result = [];
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (j === i - 1) continue;
            const value = sums.sliceSum(i, j);
            if (value < target) {
                result.push(value);
                continue;
            }
            if (value === target) {
                answer++;
            }
        }
    }

    return result;
};

const arrSums = makeSum(arr);
const brrSums = makeSum(brr);

arrSums.sort((a, b) => a - b);

const aCnt = arrSums.reduce((acc, cur) => {
    acc[cur] = (acc[cur] || 0) + 1;
    return acc;
}, {});
const bCnt = brrSums.reduce((acc, cur) => {
    acc[cur] = (acc[cur] || 0) + 1;
    return acc;
}, {});

const a = [...new Set(arrSums)];
const b = [...new Set(brrSums)];

for (const v of b) {
    let s = 0;
    let e = a.length - 1;
    while (s <= e) {
        const mid = Math.floor((s + e) / 2);
        const valueArr = a[mid];
        const total = valueArr + v;
        if (total === target) {
            answer += aCnt[valueArr] * bCnt[v];
            break;
        }
        if (total > target) {
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }
}

console.log(answer);