[BaekJoon] 8111번 0과 1 (Java) 문제 풀이 [Platinum 5]

문제

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

 

어떻게 풀 것인가?

우선 문제를 읽으면서 수를 보며 잠깐 수학개념에 대해서 생각을 하다가, "어? BFS문제로 풀릴거 같은데?" 라는 생각으로 접근하였다. 하지만 문제가 풀리지 않아서 다른 분의 풀이를 결국엔 참고할 수 밖에 없었다. 맨 아래에 참고했던 블로그들의 링크를 걸어 두었다. 그래도 내가 이해한 것을 기반으로 작성해보자.

 

모듈러 법칙을 활용한 BFS 접근법 정리:

이 문제는 주어진 수 N 으로 나누어 떨어지는 0과 1로 이루어진 가장 작은 수를 찾는 문제다. 단순히 BFS로 숫자를 확장하는 것만 생각하면 해결하기 어렵지만, 모듈러 연산의 특성을 이용하면 효율적인 탐색이 가능하다.

 

모듈러 법칙 활용

• 어떤 수 A 를 B 로 나눈 나머지를 C 라고 할 때: (A mod  B)=C ⇒ (C mod  B) =C
• 여기서 중요한 점은 같은 나머지를 갖는 수들은 동일한 연산을 적용해도 같은 나머지를 유지한다는 것이다.
• 즉, 숫자에 0을 붙이는 연산은 ×10, 1을 붙이는 연산은 ×10+1로 표현할 수 있다.
• 따라서 어떤 수 X 가 특정한 나머지를 가진다면, 거기에 0이나 1을 붙여도 나머지 연산 결과는 일정한 패턴을 따른다.

BFS 탐색 방식

• BFS를 활용하여 숫자를 확장하면서 나머지를 계산하고, 이미 방문한 나머지는 다시 탐색하지 않는다.
• 숫자의 길이가 증가해도 나머지 값의 종류는 최대 N−1 개뿐이므로, 방문 체크 배열(visited)의 크기는 N 만큼만 사용하면 된다.
• 즉, 불필요한 연산을 줄이며 효율적으로 탐색할 수 있다.

결과

• BFS 과정에서 문자열을 함께 저장하여, 나머지가 0이 되는 순간 해당 문자열을 출력하면 된다.
• 같은 나머지가 다시 나올 일이 없으므로, 중복 탐색 없이 최적의 해를 찾을 수 있다.

이 방법을 활용하면 최대 20,000까지 가능한 N 에 대해 빠르게 정답을 찾을 수 있다.

 

풀면서 놓쳤던점

수학 모듈러의 법칙

 

이 문제를 통해 얻어갈 것

모듈러의 법칙?을 활용한 BFS 접근

 

내 코드 

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < T; i++) {
			int N = Integer.parseInt(br.readLine());
			sb.append(BFS(N));
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}

	public static String BFS(int num) {
		Queue<Pair> queue = new ArrayDeque<>();

		boolean[] visited = new boolean[20001];

		queue.add(new Pair("1", 1));

		while (!queue.isEmpty()) {
			Pair cur = queue.poll();
			int curNum = cur.num;
			String curStr = cur.str;
			if (curNum == 0) {
				return curStr;
			}
			if (curStr.length() > 100) {
				return "BRAK";
			}
			int plusZero = (curNum * 10) % num;
			if (!visited[plusZero]) {
				visited[plusZero] = true;
				queue.add(new Pair(curStr + "0", plusZero));
			}
			int plusOne = (curNum * 10 + 1) % num;
			if (!visited[plusOne]) {
				visited[plusOne] = true;
				queue.add(new Pair(curStr + "1", plusOne));
			}
		}
		return "BRAK";
	}
}

class Pair {
	String str;
	int num;

	public Pair(String str, int num) {
		this.str = str;
		this.num = num;
	}
}

 

참고

https://velog.io/@ouk/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8%EB%B0%B1%EC%A4%80-%EB%B0%B1%EC%A4%80-8111%EB%B2%88-0%EA%B3%BC-1-%EB%AC%B8%EC%A0%9C-Java%EC%9C%BC%EB%A1%9C-%EC%99%84%EB%B2%BD-%ED%95%B4%EA%B2%B0%ED%95%98%EA%B8%B0

[코딩테스트][백준] 🔥 백준 8111번 "0과 1" 문제: Java으로 완벽 해결하기! 🔥

https://velog.io/@solser12/%EB%B0%B1%EC%A4%80-8111-0%EA%B3%BC1-JAVA

[백준 8111] 0과1 (JAVA)