백준 1436번 영화감독 숌 C++

www.acmicpc.net/problem/1436

1436번: 영화감독 숌

 

#include <stdio.h>

bool check_666(int num) {
	while (num >= 666) {
		if (num % 1000 == 666) return true;
		num /= 10;
	}
	return false;
}

int main() {
	int n, progression; scanf("%d", &n);
	if (n <= 19) progression = 666;
	else if (n <= 280) progression = 10666, n -= 19;
	else if (n <= 3700) progression = 100666, n -= 280;
	else if (n <= 7400) progression = 1000666, n -= 3700;
	else progression = 2000666, n -= 7400;
	while (true) {
		if (check_666(progression)) {
			if (--n == 0) break;
		}
		progression++;
	}
	printf("%d\n", progression);

	return 0;
}

손으로 계산해본 결과 N이 10000일 때 2~3백만 정도 된다는 것은 알아서 1부터 돌릴까 생각했지만 그렇게 하면 시간이 너무 오래 걸릴 것 같아서 자릿수별로 나눴다.

100자리수는 666

1000자리수는 1666 2666 3666 ... 5666 6660 6661 6662 6663 ... 6669 7666 8666 9666로 18개

10000자리수는 1000자리수 앞에 1~5, 7~9가 붙은 것 -> 8 * 19(1000자리수 18개와 0666)

6만대는 60666, 61666 ... 65666까지와 67666, 68666, 69666으로 9개.

그리고 666XX. 666XX에는 66600 ~ 66699까지 총 100개가 들어갈 수 있다.

만의 자리수는 총 261개로 100,000자리수가 시작되기 위해서는 261 + 19 = 280개

N = 281일때 가장 작은 십만 자리수가 된다.

 

이런 식으로 자릿수별로 나누었는데 오히려 코드가 더 지저분해 보이는 것 같다.

시간문제라면 3700, 7400 정도로만 나눠도 됐을 것 같기도 하다.