글 읽기 - (누적합+이진탐색) 틀린 이유가 뭔지 모르겠습니다..ㅠㅠ

oio3215 2년 전 0

왼쪽 피자의 누적합,

오른쪽 피자의 누적합을 구하고

오른쪽 피자를 정렬한 후에

찾고자하는 숫자 - 왼쪽피자 누적합[0~N] 한 값을 오른쪽 피자에서 이진탐색으로 찾는 과정입니다.

왜 틀렸는지 모르겠습니다 ㅠㅠ 도와주세요.

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

const leftSum = (arr) => {
    let sum = [];
    for(let i=0; i<arr.length; i++){
        // 맨왼쪽 피자부터 누적합 구하기
        let acc = 0;
        for(let j=i; j<i+left; j++){
            let temp = j % left;
            acc += arr[temp];
            sum.push(acc);
        }
        //console.log(sum);
    }

    return sum;
}

const rightSum = (arr) => {
    let sum = [];
    for(let i=0; i<arr.length; i++){
        // 맨왼쪽 피자부터 누적합 구하기
        let acc = 0;
        for(let j=i; j<i+right; j++){
            let temp = j % right;
            acc += arr[temp];
            sum.push(acc);
        }
        //console.log(sum);
    }

    return sum;
}

const binary_search = (t, arr) => {
    let low = 0;
    let high = arr.length-1;

    while(low<=high){
        let mid = Math.floor((high+low)/2);

        if(arr[mid] === t) return true;
        else if(arr[mid] < t){
            low= mid+1;
        }else{
            high= mid-1;
        }
    }

    return false;
}

const target = Number(input[0]);
const [left, right] = input[1].split(' ').map(Number);
const pizzaLeft = [];
const pizzaRight = [];


for(let i=2; i<input.length; i++){
    if(i<2+left){
        pizzaLeft.push(Number(input[i]));
    }else{
        pizzaRight.push(Number(input[i]));
    }
}

let leftAcc = leftSum(pizzaLeft);
let rightAcc = rightSum(pizzaRight);

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

let cnt = 0;
for(let i of leftAcc){
    if(i === target) {
        //console.log(i);
        cnt++;
        continue;
    }
    if(binary_search(target-i, rightAcc) === true){
        //console.log(i, target-i);
        cnt++;
    }
}

for(let i of rightAcc){
    if(i === target) {
        cnt++;
        //console.log(`rightAcc ! i = ${i}, target = ${target}`);
    }
}

console.log(cnt);

evol2121 1년 전 0

누적합을 구하시는 과정에서 중복되는 경우가 있는거 같습니다!

피자가 3 조각으로 나누어지고, 각 조각을 1, 2, 3이라고 해봅시다. 그럼 질문자님의 코드에서는

(1), (1,2), (1,2,3)

(2), (2, 3), (2,3,1)

(3), (3,1), (3,1,2)

로 나누어지게 되는데 (1, 2, 3), (2, 3, 1), (3, 1, 2)가 중복되게 됩니다.

저도 이 경우를 고려하지 않아 문제를 틀렸는데, 혹시나 도움이 되셨길 바랍니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

(누적합+이진탐색) 틀린 이유가 뭔지 모르겠습니다..ㅠㅠ

oio3215 2년 전 0

evol2121 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말