[BOJ/백준] 16676번 : 근우의 다이어리 꾸미기 (Java)

📘 백준 16676번 : 근우의 다이어리 꾸미기

---

문제 바로가기

💡 문제 풀이

---

0부터 N까지의 모든 수를 만들기 위해 필요한 팩 수는 “어떤 숫자가 한 수 안에서 최대 몇 번 반복되는가”로 결정됨.

같은 길이의 수에서 가장 같은 수가 많이 반복되는 형태는 모든 자리의 수가 같은 수를 가지는 형태. 그 중에 최솟값은 모든 자리 수가 1인 수. (맨 앞의 자리에는 0이 올 수 없음)

예를 들어, 1111이면 4팩이 필요하지만 1110이면 3팩이 필요함. (1110인 경우, 모든 자리의 수가 같은 값을 가지는 최댓값은 999이기 때문)

따라서 N과 N의 길이(len)와 같은 길이를 가지는 111… 형태의 수를 비교.

N이 이 값보다 크거나 같으면 len만큼 필요. N이 이 값보다 작으면 len-1만큼 필요.

단, N이 0 같은 경우도 있으므로 최소 팩 수는 1이어야 함.

✅ 코드 (Java)

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// https://www.acmicpc.net/problem/16676
// 0부터 N까지의 모든 수를 만들기 위해 필요한 팩 수는 가장 많이 반복되는 경우는 보통 111... 형태의 수를 기준으로 다름
// N의 자릿수를 len이라 할 때 len자리의 111...과 비교해서 크거나 같으면 111...이 포함되므로 len만큼 필요
// 그 값보다 적으면 최대 len -1만큼 필요
// 단, 최소 1만큼 필요
public class B16676_근우의_다이어리_꾸미기 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String N = br.readLine(); // 정수 N
		int len = N.length(); // N의 길이
		int oneone = 0; // N의 길이만큼의 111...
		int tenSquare = 1; // oneone을 구하기 위한 10의 제곱수
		for (int i = 0; i < len; i++) { // oneone 구하기
			oneone += tenSquare;
			tenSquare *= 10;
		}
		// N이 oneone보다 크면 N의 길이만큼 필요, 아니면 N의 길이 - 1 만큼 필요
		int ans = (Integer.parseInt(N) >= oneone) ? len : len - 1;
		ans = Math.max(ans, 1); // 최소 1개 필요
		System.out.println(ans); // 출력
		br.close();
	}
}

💾 제출 결과

---

보러 가기