[백준] 1436. 영화감독 슘

문제

풀이

찾은 규칙은 다음과 같다.

• prefix를 0부터 시작해서 유지하고 1사이클이 끝나면 prefix를 증가시킨다.
• 처음 0~5까지는 prefix와 666사이에 붙힌다. ex) 1666, 2666, 11666
• prefix 6이 나오면 뒤에서 만들 수 있는 조합의 개수가 늘어남 
  ex) prefix 1 => 뒤에 10개 / prefix 16 ⇒ 뒤에 100개 / prefix 166 ⇒ 뒤에 조합 1000개
• 결론은 1사이클은 6 + (10^prefix의 6의 개수) + 3 의 규칙을 가지게 된다.

다 푼뒤에 생각해보니 Input이 작아서 1부터 모든 수를 돌며 666이 포함될 경우 카운트 하는 방법도 가능할 것 같다.

import java.util.Scanner;

public class Solution {
	private static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int N = sc.nextInt() - 1;

		if (N == 0) {
			System.out.println("666");
			return;
		}

		int prefix = 0;
		int cnt;
		while (true) {
			cnt = 1;
			if (prefix % 10 == 6)
				cnt++;
			if (prefix % 100 == 66)
				cnt++;

			int limit = (int) Math.pow(10, cnt) + 9;
			if (N / limit == 0)
				break;

			N -= limit;
			prefix++;
		}

		String body = "";
		for (int i = 3; i >= cnt; i--) {
			body += "6";
		}
		
		StringBuilder sb = new StringBuilder();

		if (prefix != 0) {
			sb.append(String.valueOf(prefix));
		}

		if (N < 6) {
			sb.append(N + "666");
		} else {
			int limit = (int) Math.pow(10, cnt) + 6;
			if (N < limit) {
				sb.append(body + getFormatNum(cnt, N - 6));
			} else {
				sb.append((N - (int) Math.pow(10, cnt) + 1) + "666");
			}
		}
		
		System.out.println(sb.toString());
		
	}
	
	private static String getFormatNum(int len, int target) {
		StringBuilder sb = new StringBuilder();
		sb.append(String.valueOf(target));
		for (int i = sb.length(); i < len; i++) {
			sb.insert(0, '0');
		}
		return sb.toString();
	}

}