[백준] 31288번: 캬루 Java

사실 캬루가 무슨 캐릭터인지는 잘 모르겠다

 

문제

이번에 캬루는 소수를 배신했다. 소수의 한 자리를 바꾸어서 소수가 아니게 만들어버렸다. 구체적으로는, 0으로 시작하지 않는 N자리 소수 P에 대해 어떤 수 Q가 P-캬루라는 것은 다음을 모두 만족하는 것을 의미한다.
• Q는 2 이상의 N자리 정수이며, 0으로 시작하지 않는다.
• P와 Q의 서로 다른 자릿수는 하나뿐이다.
• Q는 소수가 아니다.
다음은 N=2, P= 19일 때 P-캬루와 P-캬루가 아닌 수의 예시이다.
• Q = 9는 1자리 정수이므로 19-캬루가 아니다. 09처럼 수가 0으로 시작할 수는 없다.
• Q = 92는 P = 19와 서로 다른 자릿수가 두 개이므로 19-캬루가 아니다.
• Q = 29는 소수이기 때문에 19-캬루가 아니다.
• Q = 16,49 등은 19-캬루이다.
N자리 소수 P가 주어졌을 때, P-캬루인 수가 적어도 N개 있다는 것을 증명할 수 있다. 이 N개의 수를 직접 찾아보자.
 

입력

입력 첫째 줄에 테스트 케이스의 수가 주어진다. (1 ≤ T ≤ 3545)
각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에는 문제의 N과 P가 공백으로 구분되어 주어진다.
(1 ≤ N ≤ 100; 10^(N-1) ≤ P < 10^N; P는 소수)
주어지는 모든 N의 합은 3545 이하이다.
 

출력

각 테스트 케이스마다 N개의 줄을 출력한다.
i번째 줄에는 Q_i와 R_i를 공백으로 구분하여 출력한다. Q_i는 서로 다른 P-캬루들이며,
R.는 2 ≤ R_i < Q_i 인 Q_i의 약수이다.
 

접근

한자리 수가 다른 소수가 아닌 수와 약수를 출력해야 한다.
 
우선 각 배수의 특징을 알아보자

• 2의 배수 : 모든 짝수는 2의 배수
• 3의 배수 : 자릿수의 합이 3의 배수이면 해당 수는 3의 배수
• 4의 배수 : 마지막 두 자리가 00, 04, 08, 12, 16, 20, ... 등 4의 배수인 수
• 5의 배수 :  0 또는 5로 끝나는 수
• 8의 배수 : 마지막 세 자리가 000, 008, 016, 024, ... 등 8의 배수인 수
• 9의 배수 : 자릿수의 합이 9의 배수이면 해당 수는 9의 배수
• 10의 배수 : 0으로 끝나는 수

이 중 모든 자리수의 합이 3의 배수이면 3의 배수라는 성질을 이용한다.
 
먼저, 소수의 모든 자리수를 합쳐 3으로 나눈 나머지값(@)을 구한다.
만약 주어진 소수의 어느 자리수에서 @를 뺀다면, 모든 자리수의 합은 3의 배수가 됨으로, 이는 3의 배수이다.
따라서 각 자리수를 탐색하면서 @를 뺀 수를 대신 해당 자리수에 넣는다.
이 때, @를 뺀 값이 음수이거나 0 이라면 +3을 더해 이 값을 보정한다
(0인 경우, 맨 앞자리가 아니면 문제가 되지는 않지만, 편의상 보정한다.)
 
또한 1자리 수의 경우, 3은 3의 배수이긴 하나 소수이다.
따라서, 1의 자리수인 경우에만 4로 강제적으로 지정하였다.
 

구현

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

//https://www.acmicpc.net/problem/31288
public class 캬루 {
	
	public static String solution(int n, String num) {
		StringBuilder sb = new StringBuilder();
		if(n==1) return "4 2"; //한자리 수일 경우, 3도 소수임으로 4로 고정
		//모든자리숫자의 합이 3의 배수면 3의 배수임을 이용
		//모든 자리 숫자의 합을 3으로 나눈 나머지 계산
		int remainder = 0;
		for(char c : num.toCharArray()) {
			int x = c - '0';
			remainder = (x+remainder)%3;
		}
		//각 자리수 탐색
		for(int i=0;i<n;i++) {
			//현재 수 - 나머지, 양수가 아닌 경우 +3을 더해 보정
			int x = num.charAt(i)- '0';
			int next= (x-remainder)<=0 ? (x-remainder+3) : (x-remainder);
			String front = num.substring(0, i);
			String back = num.length()-1>i ?  num.substring(i+1) : "";
			String answer = front+next+back;
			sb.append(answer +" "+" 3\n");//3으로 나뉘어 지는 값 출력
		}
		return sb.toString().trim();
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			int m = Integer.parseInt(st.nextToken());
			String num  = st.nextToken();
			sb.append(solution(m, num)+"\n");
		}
		System.out.println(sb.toString());
		br.close();
	}
}