문제

---

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

코드

---

import java.io.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		System.out.println(solve(Integer.parseInt(br.readLine())));
	}

	static int solve(int N) {
		int num = 666;

		int count = 0;
		while (true) {
			if (count == N) {
				return num - 1;
			}

			String str = String.valueOf(num);
			if (str.contains("666")) {
				count++;
			}
			num++;
		}
	}
}

문제 이해

---

• 간단하다. 666이 들어가는 숫자중에 가장 작은 숫자부터 순차적으로 구하면 된다.
• 예를 들어 666, 1666, 6661 등이 있다.
• 666이 들어가는 숫자중 N번째로 작은 숫자를 구하면 된다.

풀이 방법

---

• 666을 시작으로 while문을 통해 숫자를 1씩 증가시킨다.
• 만약 그 숫자에 666이 들어있다면, count를 증가시킨다.
• count가 N과 똑같아진다면, 마지막 숫자를 반환하고 종료한다.

핵심 포인트

---

• 브루트포스, 즉 666이 들어갈 수 있는 모든 경우에 대해서 작은 수부터 순차적으로 구해야 한다.

보완할 점 / 느낀 점

---

• 아주 예전에 이 문제를 접했다가 낭패를 당한적이 있었다.
• 문제에서는 어쨌든 666이 들어가는 숫자중 작은 숫자부터 구하면 되는 문제이기 때문에, 규칙을 찾고 적용해가면서 문제를 해결하려고 하였다.
• 하지만 계속 엣지케이스들이 맞지 않았고, 결국 코드를 찾아봤을 땐 코드가 너무 간단해서 현타도 왔었다.
• 그때 당시에서는 그 넓은 수의 범위안에서 666만 있으면 되기 때문에 이를 중점적으로 생각하면 간단히 풀릴 줄 알았으나 큰 오산이었다.
• 물론 시간 복잡도 자체는 선형이나, 어디까지나 N이 10,000까지이기 때문에 선형의 시간복잡도중에선 큰 편일 수 있다. 하지만 제한 시간 2초, 대략 2억번의 루프까진 괜찮다는 의미이기 때문에 브루트포스가 올바른 접근이라고 생각한다.

참고자료

---