BOJ 14265 영선 수열

이 문제는 k부터 시작해서 거꾸로 올라가면서 X를 찾으면 되는데, 짝수인 경우 두 갈래(*2, +1) 로 갈리므로 일일이 찾게되면 시간이 너무 많이 걸린다.
k부터 시작해서 2k, k+1,... 쭉 적어나가다 보면 규칙이 있다.

바로 (2^i * k)  ~ (2^i * k + 2^i - 1) 의 형태만 존재하게 된다.
그래서 이 것을 이용해서 구할 수 있는데, 문제가 있다. 혹시 저렇게 나가다 보면 겹치지 않을까? 결론부터 말하면 겹치지 않는다. 왜냐하면 원래 문제에서 주어진 연산 자체가 짝수이면 이것, 홀수이면 저것으로 갈래가 두 갈래 이상이 아닌 딱 한 갈래이기 때문에 거꾸로 올라가면서 겹친다는 것은 원래 연산으로 내려올 때 갈래가 두 갈래 이상이 된다는 것이므로 모순이다.

그리고 저 위에 적은 형태는 엄밀히 말하면 k가 홀수일 경우에 완벽히 적용되고, k가 짝수이면 조금 다르다. k가 짝수인 경우는 해보면 처음부터 두 갈래로 갈리는데, 2*k갈래를 따라가면 저위의 형태만 존재하게 되지만 k+1갈래 쪽은 저렇지 않다.
여기서 방법이 두 가지가 있는데, k+1을 k'로 보는 것이다. 그럼 위의 형태와 똑같이 된다.
그래서 계산할 때 k가 짝수인 경우는 두 갈래를 따로 구해서 더해주는 방법이 있고,
또 하나는 백준님의 코드를 보고 알게된 것인데, k+1갈래 쪽도 더 그려보면 규칙이 있다.
바로 (2^i * k + 2^i) ~ (2^i * k + 2^(i+1) -1) 의 형태만 존재한다는 것. 즉 두 갈래 전체를 보면 (2^i * k) ~ (2^i * k + 2^(i+1) -1) 의 형태로 존재하게 된다.
이 것을 구현하는 것은 그렇게 어렵지는 않다. 그냥 lo=k, hi=k에서 시작해서 lo에는 *2, hi에는 *2 + 1을 해주는데, k가 짝수인 경우는 처음 시작할 때 ㅣlo=k, hi=k+1에서 시작하면 된다.

그리고 나는 2의 n제곱수들을 미리 계산해서 배열에 넣어놓고 썼는데, 굳이 그럴 필요가 없다. 그냥 lo, hi에 각각 *2, *2+1을 해주면서 나가면 된다...

그리고 또 나는 문제에서 주어진 X의 범위, a, b에 맞는 경우만 개수를 세느라 구현이 좀 더 복잡해지기도 하고 실수도 해서 계속 틀렸었는데, 그냥 (0~b까지의 경우) - (0~a까지의 경우)를 해주면 된다... 이렇게 하면 정말 구현도 편해지고 나처럼 실수할 가능성도 적을 것이다.