[BOJ 14686 // C++] Sum Game

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 14686번 문제인 Sum Game이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/14686

14686번: Sum Game

이 문제는 Prefix Sum에 입문하기 좋은 문제이다.

 

글쓴이는 이 문제를 다음과 같이 해결했다.

 

1) 크기 10만의 배열을 준비하고 Swifts 팀의 경기 점수의 prefix sum을 배열에 채워넣는다.

2) prefix sum을 계산할 정수를 선언하고, 들어오는 Semaphores 팀의 경기점수를 더해가면서 미리 준비한 배열과 값이 같은지 비교해나간다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;
int games[100000];

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;
    for (int i = 0;i < N;i++) { // Swifts 팀의 prefix sum array 만들기
        int x;
        cin >> x;
        if (i == 0) games[i] = x;
        else games[i] = games[i - 1] + x;
    }
    int prefixsum = 0; // Semaphores 팀의 prefix sum
    int ans = 0;
    for (int i = 0;i < N;i++) {
        int x;
        cin >> x;
        prefixsum += x;
        if (prefixsum == games[i]) ans = i + 1; // 두 팀의 prefixsum이 같을 때 i+1을 반환, 없다면 0이 유지됨
    }
    cout << ans;

    return 0;
}