크리스마스 선물을 풀어보기

이런 저런 핑계를 대며 '꾸준한 백준 풀이'를 멈춘지 벌써 반년이 되었다. 학기 중에는 자료구조 과제로 나온 20개의 문제가 나의 경진 프로그래밍 감각을 유지해주는 역할을 하고 있다고 애써 타협해왔는데, 궁색한 변명이었음이 오늘 드러났다. 크리스마스 당일날 이 문제를 풀었다면 정말 내 생애 가장 끔찍한 크리스마스가 되지 않았을까.
https://www.acmicpc.net/problem/3131

3131번: 크리스마스 선물

시간 복잡도를 고려했을 때 가능한 방법이 뭘까 하는 고민 끝에, 4개의 누적 합 배열을 사용하는 방법을 떠올린 것까지는 좋았다. 그 이후로 조건에 따라 각 배열에 접근하기 위한 index 번호를 부여하는게 여간 어렵지 않았다. 라고 생각했지만 그건 내가 암산으로만 모든 것을 해결하려 했기 때문이었음이 드러났다. 몇 시간의 삽질 끝에 오기를 버리고, 메모장을 켜서 테스트케이스를 바탕으로 규칙성을 찾아낼 수 있었다. 일반화된 수식으로 생각할 깜냥이 안 되면, 구체적인 사례로부터 일반화를 이끌어내는게 훨씬 효율적이라는 걸 깨달았다. 그걸 깨닫기까지 문제 생각을 하지 않고 있는 동안에도 머리가 너무 지끈거렸다. 쓸데없이 머리에 과부하를 준 것 같다.

프로그래머라면 손가락을 키보드에만 갖다대고 모든 문제를 다 해결할 것이라는 환상에 빠져 있었던 듯하다. 직관으로 바로 이해되는 단계를 넘어서는 복잡한 논리 구조라면 시각화가 필요할 텐데. 급할수록 돌아가는게 맞듯이, 알고리즘 문제 풀이를 할 때나 프로그램을 설계할 때에도 직접 그림이나 글로 나타내는 것이 맞겠다.

/*-------------------------------------
Project Name : Baekjoon
File Name : 3131.cpp
Revision : 0.1
Date : 2021.12.28
Author : Starsein
-------------------------------------*/
#include <iostream>
#include <vector>
#include <set>
using namespace std;
#define pb push_back

int a, b, n;
long numCases = 0;
const long PRICE_LIMIT = 10e9;
vector<int> v_num;                         // v_num : 내림차순으로 정렬된 가격의 배열
vector<long> v_prefSumA(1), v_prefSumB(1); // v_num의 왼쪽에서부터 구한 누적합의 배열 (A : 짝수 인덱스, B : 홀수 인덱스)
vector<long> v_suffSumA(1), v_suffSumB(1); // v_num의 오른쪽에서부터 구한 누적합의 배열 (A : 짝수 인덱스, B : 홀수 인덱스)
set<long> s_IVchecked;                     // 가짜 가격의 경계값 중복 여부 확인을 위한 집합

void Input() {
    cin >> a >> b >> n;
    int inp;
    for (int i = 0; i < n - 1; i++) {
        cin >> inp;
        v_num.pb(inp);
    }
}
void Make2PrefixSum() {
    for (int i = 0; i < n - 1; i++) {
        if (i % 2 == 0) {
            v_prefSumA.pb(v_prefSumA.back() + v_num[i]);
        } else {
            v_prefSumB.pb(v_prefSumB.back() + v_num[i]);
        }
    }
}
void Make2SuffixSum() {
    for (int i = n - 2; i > -1; i--) {
        if (i % 2 == 0) {
            v_suffSumA.pb(v_suffSumA.back() + v_num[i]);
        } else {
            v_suffSumB.pb(v_suffSumB.back() + v_num[i]);
        }
    }
}
long CountCases(int i, long dist) {
    long res = 0, lb = 0, ub = 0, liv = 0, uiv = 0; 
    /*
    lb : LowerBound - 가짜 가격이 v_num의 특정 위치에 올 때 그 하한값
    ub : UpperBound - 가짜 가격이 v_num의 특정 위치에 올 때 그 상한값
    # lb와 ub는 가짜 가격이 v_num의 특정 위치에 존재하기 위한 조건
    liv : LowerIntervalValue - 위 조건과 문제의 조건을 만족하는 가짜 가격의 하한값
    uiv : UpperIntervalValue - 위 조건과 문제의 조건을 만족하는 가짜 가격의 상한값
    */
    if (0 < i && i < n - 1) {
        lb = v_num[i];
        ub = v_num[i-1];
    } else if (i == 0) {
        lb = v_num[i];
        ub = PRICE_LIMIT;
    } else {
        lb = 1;
        ub = v_num[i-1];
    }
    if (i % 2 == 0) {
        liv = max(lb, a - dist);
        uiv = min(ub, b - dist);
    } else {
        liv = max(lb, dist - b);
        uiv = min(ub, dist - a);
    }
    if (liv <= 0 || uiv <= 0) return 0;
    if (liv > uiv) return 0;

    res = uiv - liv + 1;
    if (s_IVchecked.find(uiv) != s_IVchecked.end()) res -= 1;
    s_IVchecked.insert(liv);

    return res;
}

void Calculate() {
    if (n == 1) {
        numCases = b - a + 1;
        return;
    }
    
    long sumOB, sumYB, dist; // sumOB : 형의 총합(가짜 가격 제외)
                             // sumYB : 동생의 총합(가짜 가격 제외)
    if (n % 2 != 0) {
        for (int i = 0; i < n; i++) {
            sumOB = v_prefSumA[(i+1)/2] + v_suffSumB[(n-i)/2];
            sumYB = v_prefSumB[i/2] + v_suffSumA[(n-i-1)/2];
            dist = sumOB - sumYB;
            numCases += CountCases(i, dist);
        }
    } else {
        for (int i = 0; i < n; i++) {
            sumOB = v_prefSumA[(i+1)/2] + v_suffSumB[(n-i-1)/2];
            sumYB = v_prefSumB[i/2] + v_suffSumA[(n-i)/2];
            dist = sumOB - sumYB;
            numCases += CountCases(i, dist);
        }
    }
}
void Output() {
    cout << numCases;
}

int main() {
    Input();
    Make2PrefixSum();
    Make2SuffixSum();
    Calculate();
    Output();
    return 0;
}

문제 푸는 내내, 알고리즘 자체는 간단한데, 디테일을 구현하는 데에서 막히고 있다는 사실이 괴로웠다. 그래도 포기하지 않고 결국 맞혀서 자신감을 선물로 얻었다.


* 새로운 습관
1. 코딩하기 전에 볼펜과 종이, 최소한 시각화를 돕는 프로그램(그리기 도구 또는 메모장)을 준비하자.
2. 머릿속에 떠오른 이미지나 논리를 그림이나 글로 나타내어 보자.