백준 6200, Dynamic Programming
USACO November 2007 Contest silver 3번 문제.
문제를 푸는 아이디어 접근은 성공했지만, off by one error 가 많아서 오래 걸린 문제다.
구현을 정확히 하는 연습이 많이 필요하다고 매번 느낀다.
문제를 푸는 아이디어는 간단하다.
경우의 수를 세 가지로 나누어서 풀면 된다.
1.숫자 $N$ 보다 작은 $2^k$ 까지 round number 의 개수
2.$2^k$ 보다 크고 $N$ 보다 작거나 같은 round number 의 개수
3.주어진 $N$ 이 round number 인지 확인
Source Code
//BOJ 6200
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll S, E;
ll combination[40][40];
void getcombination() {
//nCr 구하기.
//31C15 를 해도 int 범위 넘어가지 않는다. 애초에 정답이 int 범위 이내.
combination[0][0] = 1;
combination[1][0] = 1;
combination[1][1] = 1;
for (int i = 2; i < 35; ++i) {
for (int j = 0; j <= i; ++j) {
if (j == 0 || j == i) {
combination[i][j] = 1;
continue;
}
combination[i][j] = combination[i - 1][j - 1] + combination[i - 1][j];
}
}
}
struct bitlist {
//barr : num의 이진수 형태 저장.
bool barr[35];
ll num;
bitlist() {
memset(barr, 0, sizeof(barr));
num = 0;
}
};
bitlist numproc(ll n) {
bitlist ret;
ret.num = n;
for (int i = 0; i < 35; ++i) {
ret.barr[i] = n % 2;
n /= 2;
}
return ret;
}
ll roundnum(bitlist n) {
ll ret = 0;
ll spoint = 0;
//N 보다 작거나 같은 2^k 까지의 round number 개수.
for (ll i = 0; i <= 31; ++i) {
ll tmp = ((ll)1 << (i));
spoint = i;
if (n.num >= tmp) {
for (ll j = 0; (j + 1) <= i / 2; ++j) {
ret += combination[i-1][j];
}
}
else break;
}
--spoint;
//N 보다 큰 round number 개수.
//spoint-1 부터 0 번째 index 에 bit 가 켜져있다면
//그 비트를 0으로 만들고, 그 밑의 자리 수로 만들 수 있는 round number의 개수를 센다.
//이 때 round number 의 개수는 앞에 있는 0 과 1의 개수(cntone, cntzero) 에 의존한다.
for (ll i = spoint - 1; i >= 0; --i) {
if (!n.barr[i]) continue;
ll cntone =0, cntzero=0;
for (int j = spoint; j >= i; --j) {
if (n.barr[j]) ++cntone;
else ++cntzero;
}
--cntone; ++cntzero;
for (ll j = 0; 2*(j + cntone) <= (spoint+1) ; ++j) {
ret += combination[i][j];
}
}
//마지막으로 주어진 수가 round number 인지 확인.
ll cntone = 0, cntzero = 0;
for (ll i = spoint; i >= 0; --i) {
if (n.barr[i]) ++cntone;
else ++cntzero;
}
if (cntone <= cntzero) ++ret;
return ret;
}
int main() {
cin >> S >> E;
if (S > 1) --S;
getcombination();
bitlist s, e;
s = numproc(S);
e = numproc(E);
printf("%lld\n", roundnum(e) - roundnum(s));
return 0;
}