[BOJ] 1494 절댓값 수열

문제#

어떻게 풀었나?#

$S_0 = A,\; S_1=a$라 두고 숫자를 쭉 나열해보면 아래와 같이 a가 계속 반복됨을 알 수 있다.

A
a
A-a
A-2a
a
A-3a
A-4a
a
A-5a
A-6a
...

그리고 중간에 A-6a 형태로 썼지만, 사실 A가 6a보다 커야 A-6a인거고 중간에 A-4a부터 음수가 되었다 하면, 4a-A로 그 결과가 달라질 것이다. 그러므로 $A \ge 2a\cdot s$를 만족하는 $s$를 찾으면 현재 $S_k$를 보고 있다고 할 때, $S_{k+3s}$까지 건너뛸 수 있다. 이 부분이 메인 아이디어고, 그 외에는 건너뛰지 않고 1 step씩 다음 $S_i$를 구하면 된다.

추가로 a가 0일 땐 A다음 a가 나오는 형태가 그대로 유지된 채로 현재 step + 3의 배수만큼 건너뛸 수 있다.

이를 코드로 구현하면 아래와 같다.

정답 코드#

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
inline ll ABS(ll x) {
    return (x<0LL)?-x:x;
}
ll N;
ll f(ll A, ll a, ll n) {
    ll rmn = N-n;
    if(rmn == 0) return A;
    else if(rmn == 1) return a;
    else if(rmn == 2) return ABS(A-a);
    else {
        if(a==0) {
            return f(A, a, n+(rmn/3LL)*3LL);
        }
        ll mxs = A/(2*a);
        if(mxs==0LL) {
            return f(a,ABS(A-a),n+1);
        }
        else {
            ll lo=1, hi=mxs;
            while(lo<=hi) {
                ll mid = (lo+hi)/2;
                if(n+3*mid<=N) lo=mid+1;
                else hi=mid-1;
            }
            ll s = lo-1;
            return f(A-2*a*s, a, n+3*s);
        }
    }
    
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    ll s0, s1;
    int n;
    cin >> s0 >> s1 >> n;
    for(int i=0; i<n; i++) {
        cin >> N;
        printf("%lld\n", f(s0,s1,0));
    }
    return 0;
}

Comment#

유클리드 알고리즘, Modular Inverse관련해서 공부하다가 관련 문제가 없을까 해서 boj에서 하나 골라서 푼건데, 전혀 유클리드 알고리즘과 상관없는 방식으로 풀었다. ‘난이도 기여’에 나온 사람들의 의견을 보니 확장 유클리드 알고리즘을 사용해서 풀 수도 있는 것 같다.

내가 풀 때는 플래티넘1 문제였는데, 그 정도 난이도는 아닌 것 같고 플래티넘3-5 수준의 문제가 아닐까 싶다. 내가 플3으로 난이도 평가를 했더니 해당 문제 난이도가 플2로 낮아졌다. 코포로 따지면 Div2. 1500-1750 수준의 문제가 아닐까 싶다.