글 읽기 - 두 개의 코드 중 하나는 되고 하나는 안되는데 이유가 뭘까요?

oio3215 2년 전 0

안녕하세요.

부분 누적합을 담고 두 누적합 또는 하나의 누적합 안에서 목표 값을 찾고자 합니다.

처음에는 부분 누적합을 담은 배열을 이용해 아래의 첫 번째 코드로 했으나

9%에서 실패가 떴었습니다. 여러 테스트케이스를 생각해서 돌려봤지만 제대로 나와서.. 반례를 도저히 모르겠습니다 ㅜㅜ..

그리고, 딕셔너리로 할 수 있겠다 싶어 딕셔너리로 해보았는데, 잘 작동합니다.

기본적인 원리 자체는 target값을 그대로 찾아내는 방법 똑같은데, 왜 이진탐색은 안될까요 ㅠㅠ?

제 생각에는 제 이진탐색 알고리즘 문제인 것 같기도한데... 어느부분이 문제인지도 모르겠습니다.

제발 도와주세요..

// 첫 번째 코드( 이진 탐색으로 목표 값 찾기 )

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


/* 목표 값 찾기 */
const binary_search = (target, array) => {
    let low = 0;
    let high = array.length-1;

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

        if(array[mid] === target) return true;

        if(array[mid] < target) low = mid+1;
        else high = mid-1;
    }

    return false;
}

const N = input.shift();

const A_Length = input.shift();
let A = input[0].split(' ').map(Number);
input.shift();
const B_Length = input.shift();
let B = input[0].split(' ').map(Number);


/* A의 연속되는 부분 누적합 */
const A_sum = [];
for(let i=0; i<A_Length; i++){
    let idx = 0;
    for (let j=i; j<A_Length; j++){
        idx += A[j];
        A_sum.push(idx);
    }
}

/* B의 연속되는 부분 누적합 */
const B_sum = {};
for(let i=0; i<B_Length; i++){
    let idx =0;
    for (let j=i; j<B_Length; j++){
        idx += B[j];
        B_sum.push(idx);
    }
}

/* B 정렬 */
B_sum.sort((a, b)=> a-b);

let cnt = 0;

/* target 값을 구해서 목표 값 찾는 함수에서 찾으면 cnt+1 */
for(let i=0; i<A_sum.length; i++){
    let target = N-A_sum[i];
    
   // console.log(N, A_sum[i], target);

    if(binary_search(target, B_sum) === true) cnt ++; 
}

console.log(cnt);


////////////////////////////////////////////////////////





// 두 번째 코드 ( 딕셔너리를 이용해 목표 값 찾기 )
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\r\n');

const N = input.shift();

const A_Length = input.shift();
let A = input[0].split(' ').map(Number);
input.shift();
const B_Length = input.shift();
let B = input[0].split(' ').map(Number);

const A_sum = [];
for(let i=0; i<A_Length; i++){
    let idx = 0;
    for (let j=i; j<A_Length; j++){
        idx += A[j];
        A_sum.push(idx);
    }
}


const B_sum = {};
for(let i=0; i<B_Length; i++){
    let idx =0;
    for (let j=i; j<B_Length; j++){
        idx += B[j];
        if(idx in B_sum) B_sum[idx] += 1;
        else B_sum[idx] = 1;
    }
}

let cnt = 0;
for(let i=0; i<A_sum.length; i++){
    let target = N-A_sum[i];

    if(target in B_sum) cnt += B_sum[target];
}

console.log(cnt);

kdh6429 2년 전 1

b_sum 배열에 동일한 값이 2번 이상 들어있을때 처리가 되고 안되고의 차이 같습니다.

oio3215 2년 전 0

아이고 감사합니다ㅎㅎ

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

문제

문제

출처

ICPC

두 개의 코드 중 하나는 되고 하나는 안되는데 이유가 뭘까요?

oio3215 2년 전 0

kdh6429 2년 전 1

oio3215 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말