[백준/BOJ] 1436번 영화감독 숌 (C/C++)

백준 온라인 저지(BOJ) 1436번 영화감독 숌

https://www.acmicpc.net/problem/1436

1436번: 영화감독 숌

* 사용언어 : C언어, C++

 

1. 문제

N 이 주어졌을 때,

666 이 적어도 3개 이상 연속으로 들어가는 N 번째 수를 출력

(1 이면 666, 2 이면 1666, ...)

 

2. 풀이

규칙을 찾다가 시간을 꽤 많이 날려먹었습니다. (그리고 못 찾음)

자리 수 별로 규칙을 대강 찾긴 했는데,

그 안에서 N 번째 숫자를 찾으려면 결국 해당 자리 수에서 순차적으로 확인해야했습니다.

 

그래서 규칙을 고려하지 않고 처음부터 반복문을 사용하여 전체 탐색하도록 구현했습니다.

 

 

반복문의 끝을 정확히 알 수 없는 상태로 시작하기 때문에

for 문이 아닌 while 문을 사용하여 구현했습니다.

(idx 를 반복문 외부에 선언하고 1 씩 늘리면서 반복)

 

while 문 내에서는 idx 를 순차적으로 늘려가며 확인하게 됩니다.

만약 idx 에 '666' 이 포함되어 있다면, cnt 를 하나 늘리고 다음 idx 로 넘어가게 했습니다.

 

그렇게 cnt 를 증가시키다가 n 이 되면

답을 찾은 것 이므로 while 문을 빠져나온 후 답을 출력합니다.

 

다 풀고 나니 20ms 이 나왔는데, 약간 최적화를 해서 12ms 로 마무리 지었습니다.

(① != 대신 ^(XOR) 사용, ② idx 초기값 변경 : 0 → 666)

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
1436_영화감독 숌
1112KB	12ms
*/
#include <cstdio>

const int tg = 666;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	int n;
	scanf("%d", &n);

	int idx = tg - 1, cnt = 0, tmp;
	while (cnt < n) {
		tmp = ++idx;
		while (tmp >= tg) {
			if (!((tmp % 1000) ^ tg)) {
				++cnt;
				break;
			}
			tmp /= 10;
		}
	}

	printf("%d\n", idx);
	return 0;
}

* ^(XOR) 은 피연산자 사이에 다른 비트가 있는 자리에 1을 반환합니다. 따라서 a 와 b 가 같으면 a ^ b 는 0 이 됩니다.