글 읽기 - 주석있음) 왜 오답이 발생하는지 모르겠습니다.

themion 2년 전 0

정답 코드를 제출한 뒤 시간을 줄이기 위해 여러 방법을 시도해보고 있는데, while문의 경우에는 72% 정도에서 오답이 발생하는 반면에 for문을 사용하니 정답 처리를 얻었습니다.

어떤 부분에서 에러가 발생한 건지 알려주시면 감사합니다.

#include <algorithm>
#include <cstdio>

using namespace std;

#define SUM_LEN 500500

int A[SUM_LEN], B[SUM_LEN];

// 배열을 입력받아 모든 부분합을 구한 뒤 정렬하는 함수. 잘 작동하는 코드이므로 가림
void make_array(int a[SUM_LEN], int &len);

int main() {
    int T, a_size = 0, b_size = 0, i = 0, t;
    long long ans = 0, cnt, num;

    scanf("%d", &T);

    // 두 배열 A와 B를 입력받아 부분합을 구하고 그 수를 a_size와 b_size에 저장
    make_array(A, a_size);
    make_array(B, b_size);

    // 이 while문은 오답
    while (i < a_size) {
        // 구하고자 하는 값 T에서 A의 부분합 A[i]를 뺀 값을 t에 저장
        t = T - A[i];
        
        // 같은 A[i]가 등장하는 횟수를 계산해 cnt에 저장
        cnt = 1;
        while (t + A[i + cnt] == T) cnt++;
        
        // B에서 t의 개수를 이분탐색으로 계산해 num에 저장
        num = (upper_bound(B, B + b_size, t) - lower_bound(B, B + b_size, t));

        // ans에 cnt와 num의 곱을 더함
        ans += cnt * num;
        // 다른 A[i]가 나오는 값으로 i를 점프
        i += cnt;
    }
    
    // 이 for문은 정답
    /* for (int i = 0; i < a_size; i++) {
        t = T - A[i];
        // 각 A[i]마다 B의 부분합 중 T - A[i]의 개수를 ans에 더함
        ans += upper_bound(B, B + b_size, t) - lower_bound(B, B + b_size, t);
    } */
    
    printf("%lld\n", ans);

    return 0;
}

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

문제

문제

출처

ICPC

주석있음) 왜 오답이 발생하는지 모르겠습니다.

themion 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말