알고리즘 :: 백준 :: 1436 - 영화감독 숌

 

 

 

 

 

 

 

❔문제

🔗문제링크

🔄 문제 및 입출력 조건 파악

• 입력: N ≤ 10,000
• 출력: N번째 종말의 수

✏️ 문제풀이

함정문제입니다.

0666, 1666, 2666, 3666, 4666, 5666,
6660, 6661, …., 6669, 7666, 8666, 9666
총 19개… 그게 10666부터 11666까지…

이렇게 빠져들기 시작하면 이 문제의 함정에 빠진 것입니다 ㅎㅎ
함정에 걸리는 가장 큰 이유는 N이 10,000까지 가능해 오버플로우가 될 수도 있다고 생각하기 때문입니다.

 

단순하게 666부터 카운팅하면서 1,000으로 나머지연산(`%`)한 것이 666인 수를 찾으면 됩니다.

while (temp) {
	if (temp % 1000 == 666) {
    	answer++;
        break;
    }
	temp /= 10;
}

📝 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int N;
	cin >> N;
	
	int answer = 0;
	unsigned long long num = 665;
	while (answer != N) {
		num++;
		unsigned long long temp = num;
		while (temp) {
			if (temp % 1000 == 666) { answer++; break; }
			temp /= 10;
		}
	}
	cout << num;
}

 

🔗 코드 링크

 

참고로, 나눗셈 연산 대신에 문자열로 `.find()` 함수를 이용할 수도 있습니다.

저는 이 방법이 더 빠를 줄 알고 한 번 해봤는데 오히려 훨씬 느리네요. (24ms → 68ms)

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int N;
	cin >> N;
	
	int answer = 0, num = 665;
	string temp{to_string(num)};
	temp.reserve(10);
	while (answer != N) {
		num++;
		temp = to_string(num);
		if (temp.find("666"s) != string::npos) answer++;
	}
	cout << num;
}

 

🕧 결과