A문제: 색칠된 격자판의 조건 만족

크기 n × m의 격자에서 흰색 칸과 검은 칸이 존재하며, 각 칸은 인접한 칸 중 적어도 하나가 다른 색이어야 한다. 요구사항은 검은 칸의 수가 흰 칸보다 정확히 하나 많아야 한다.

직관적인 접근은 모든 칸을 두 가지 유형으로 나누고 조건을 검사하는 것이지만, 이는 복잡하고 비효율적이다.

실제로는 간단한 패턴으로 해결 가능하다. 첫 번째 칸을 흰색으로 설정하고, 나머지 모든 칸을 검은색으로 하면 조건을 만족한다. 이는 인접성 조건과 개수 차이를 동시에 충족하기 때문이다.

B문제: 배열 변환 가능성 판단

두 배열 a, b가 주어지며, a 배열은 -1, 0, 1만 포함된다. 인덱스 i < j인 경우, a[j] = a[j] + a[i]라는 연산을 무한히 수행할 수 있다. 이 연산을 통해 a 배열을 b 배열로 만들 수 있는지 판단한다.

핵심 아이디어는 다음과 같다:

• a[1]와 b[1]가 다르면 불가능.
• 각 위치 i에서 b[i]가 a[i]보다 크다면, 앞쪽에 1이 있어야 함 → 처음 등장하는 1의 위치 l가 i보다 작아야 함.
• b[i]가 a[i]보다 작다면, 앞쪽에 -1이 있어야 함 → 처음 등장하는 -1의 위치 r가 i보다 작아야 함.

따라서 초기에 a 배열을 읽으며 1과 -1의 최초 위치를 기록하고, b 배열을 읽으면서 조건을 검사하면 된다.

cin >> n;
int l = 0, r = 0;
for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    if (a[i] == 1 && !l) l = i;
    if (a[i] == -1 && !r) r = i;
}
bool valid = true;
for (int i = 1; i <= n; ++i) {
    if (b[i] > a[i] && (!l || l >= i)) valid = false;
    if (b[i] < a[i] && (!r || r >= i)) valid = false;
}
cout << (valid ? "YES" : "NO") << '\n';

C문제: 부분수열의 합이 0이 아닌 개수 세기

배열에서 앞이나 뒤에서 임의의 개수를 제거하여 얻을 수 있는 부분수열 중, 합이 0이 아닌 것의 개수를 구해야 한다.

초기 접근은 모든 가능한 구간을 순회하며 합이 0인지 확인하는 방식이었으나, 이는 시간 초과(TLE) 발생.

더 효율적인 방법은 누적합과 해시맵을 사용하는 것이다. 누적합 s가 이전에 등장한 적이 있다면, 그 지점부터 현재까지의 구간 합이 0이라는 의미다. 이를 이용해 유효한 시작 위치를 추적한다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, x, s = 0, ans = 0, last_pos = 0;
    unordered_map<ll, ll> prefix_sum;
    prefix_sum[0] = 0;  // 초기 누적합 0

    cin >> n;
    for (ll i = 1; i <= n; ++i) {
        cin >> x;
        s += x;
        if (prefix_sum.count(s)) {
            last_pos = max(last_pos, prefix_sum[s] + 1);
        }
        ans += i - last_pos;
        prefix_sum[s] = i;
    }

    cout << ans << '\n';
    return 0;
}

이 알고리즘은 O(n) 시간 복잡도로 문제를 해결하며, 누적합의 반복 여부를 통해 유효한 구간의 시작점을 관리한다.