BOJ 14265 영선 수열

영선 수열 (14265)

https://www.acmicpc.net/problem/14265 (BOJ)

이 문제는 2017 1월에 하는 캠프문제다.

캠프참가자가 아니면 볼 수 없다.

이 문제를 올리는 이유는 내가 실수라고 떠벌리는,

어떻게 보면 사소하지만 매번  실수 하는 부분을 정리하기 위해서다.

내가 코딩하면서 가장 많이 헷갈려하는 부분이 몇 개 있는데,

인덱스의 미묘한 차이가 중요한 코딩과

반복문에서 일정 범위 사이에서 리턴 후 증가된 i를 줄여야 할 때이다.

말로만 하면 무슨 상황인지 모르니까 예를 들어보겠다.

를 입력받았을 때, 을 만족하는 가장 작은 을 구한다고 해보자.

보통 이런 코딩은 ps를 할 때에도 많이 필요하고... 특히 세그 경계 구할 때 필요하다.

세그를 4*N으로 그냥 잡아도 되지만, full-binary tree로 반드시 구현해야 할 때에는 꼭 정확한 경계를 구해야 한다.

(그런경우는 사실 거의 없긴 하지만.. 아무튼...)

이런거 고민도 안하고 후다닥 넘어가는 사람도 있지만 나는 매번 헷갈려 한다.

그 동안은 보통 아래와 같은 방식으로 코딩했다.

long long f(long long x) {
    if(x==0LL) return 0LL;
    int i=0;
    for(;(1LL<<i)<x; i++);
    return 1LL<<i;
}

아 정말 보기 싫다.

최근에 그나마 이러한 코딩 방법을 안헷갈리게 sgc님이 도와주셨는데,

binary search할 때 while(lo<hi) 형태로 짜게 되면 반드시 결과는 lo==hi에서 끝난다는 것이다.

위의 6줄짜리 코드에서도 1LL<<i값이 x이상일 때에만 반복문이 종료되는 것을 알 수 있다.

그니까 내가 하고 싶은 얘기는 부등호를 '<'를 써야 하는지 '<='를 써야 하는지를 헷갈리지 않고 바로 쓸 수 있다는 것이다.

(이런거 나만 헷갈려 했나 ㅠㅠ?)

하지만 방법이 좋지 않다.

우리가 수학적으로 기호를 표현할 때에도 절대 저따구로 표현하지 않는다.

만약 내가 (1LL<<i)<x를 만족하는 동안의 i값만 궁금해 했다면,

결과적으로 봤을 때 i값이 1증가된 상태로 나오기 때문에, 이 i값을 쓰길 원한다면 최종적으로 1을 빼줘야 한다.

그냥 코드를 직관적으로 보려해도 i값이 한눈에 들어오지 않을 수 있다. ㅠ (나는 안들어옴.. ㅠㅠ)

근데 여기에는 또 문제가 있다.

만약 i가 -1이 되어선 절대 안되는 경우가 있다면...?

밑에 또 조건문으로 처리해줘야 한다.

별거 아닌거 같지만,

이런 경우는 아주 쉬운 코포 문제에서도 많은 시간을 잡아먹게 하고..

뻑하면 sysfail을 경험하는 나로써는 고쳐야할 나쁜 습관이 아닐 수 없다. ㅠㅠ

암튼 서론이 길었는데, 이번에 캠프문제인 "영선수열"이라는 문제를 풀면서 갑자기 뭔가 정리가 됐다.

그래서 위와 같은 코딩 스타일을 아래와 같이 바꿔봤다.

long long f(long long x) {
    for(int i=0; (1LL<<0)<=x; i++) {
        if((1LL<<i)<=x && x<(1LL<<(i+1))) return 1LL<<i;
    }
    return 0LL;
}

크... 좋다 좋아

물론 반복문이 무한히 돌지 않기 위해서는 어떤 조건이나 반복문을 돌기전에 예외처리를 해야겠지만,

코드가 매우 직관적이다. 특히 for문 가운데에 들어가 있는 조건문을 빼버리고, 앞에서 if(x==0) return 0LL;을 추가하고

해당 조건문 자리를 debugging용으로 요긴하게 쓸 수 도 있다. (cnt변수를 10으로 설정한 다음에 cnt-- 를 조건문에 넣어준다거나 ? ㅎ)

그래서 위와 같이 영선 수열을 코딩해 봤다.

#include <cstdio>
using namespace std;
typedef long long ll;
ll get(ll k, ll x, ll even) {
    if(x<0||k>x) return 0;
    if(k==0) return x+1;
 
    for(ll i=0,ret=0;;ret+=(1LL<<(i++ +even))) {
        if(k*(1LL<<i)<=x && x<k*(1LL<<(i+1))) {
            ll r = x-k*(1LL<<i)+1LL;
            if(r<=(1LL<<(i+even))) return ret+r;
            else return ret+(1LL<<(i+even));
        }
    }
    return 0ll;
}
int main() {
    ll k,a,b;
    scanf("%lld%lld%lld",&k,&a,&b);
    printf("%lld\n", get(k,b,!(k&1)) - get(k,a-1,!(k&1)));
    return 0;
}