BOJ 6200

 

백준 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

6200링크


//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;
}

wbjeon2k

Pursuite for Progress.

This work is licensed under a Attribution-NonCommercial 4.0 International license. Attribution-NonCommercial 4.0 International