(JAVA) 백준 1769번 : 3의 배수

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

1769번: 3의 배수

문제

문제가 잘 풀리지 않을 때, 문제를 바라보는 시각을 조금만 다르게 가지면 문제가 쉽게 풀리는 경험을 종종 해 보았을 것이다. 여러 가지 방법이 있지만 그 중 하나로 우리가 풀고 싶은 문제를 좀 더 쉬운 문제로 바꾸어 풀어 보는 방법이 있다.

소위 "다른 문제로 바꾸어 풀기"라는 이 방법은, 아래와 같은 과정으로 이루어진다.

1. 풀고자 하는 문제를 다른 문제로 변환한다.
2. 변환된 문제의 답을 구한다.
3. 구한 답을 원래 문제의 답으로 삼는다.

이를 보다 쉽게 이해하기 위해서, 다음의 초등학교 수학 수준의 예를 들어 보자.

문제 1. "양의 정수 X는 3의 배수인가?"

이 문제를 아래와 같이 변환하는데, X의 각 자리의 수를 단순히 더한 수 Y를 만든다. 예를 들어 X가 1107이었다면, Y는 1+1+0+7=9가 된다. 그리고 Y에 대해서, 아래와 같은 문제를 생각한다.

문제 2. "Y는 3의 배수인가?"

위의 문제 1의 답은 아래의 문제 2의 대답과 일치한다. 위의 예의 경우, Y=9는 3의 배수이므로 X=1107 역시 3의 배수가 되는 것이다. 214는 각 자리수의 합 2+1+4=7이 3의 배수가 아니므로 3의 배수가 아니다.

문제 1을 풀고 싶으면 문제 2로 변환을 해서 문제 2의 답을 문제 1의 답으로 삼으면 된다. 일반적으로 Y는 X보다 크기가 작으므로, 문제 2가 더 쉬운 문제가 된다.

당신이 알고 있는 3의 배수는 한 자리 수밖에 없다고 가정하자. 즉, 문제 변환의 과정을 여러 번 거치다 보면 Y가 한 자리 수가 되는 순간이 있게 되는데, 그렇게 될 때까지 문제 변환을 반복한다는 뜻이다. 변환 후의 Y가 3, 6, 9 중 하나이면 원래의 수 X는 3의 배수이고, Y가 1, 2, 4, 5, 7, 8 중 하나이면 원래의 수 X는 3의 배수가 아니다.

큰 수 X가 주어졌을 때, 앞에서 설명한 문제 변환의 과정을 몇 번 거쳐야 Y가 한 자리 수가 되어, X가 3의 배수인지 아닌지를 알 수 있게 될지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 큰 자연수 X가 주어진다. X는 1,000,000자리 이하의 수이다. 수는 0으로 시작하지 않는다.

출력

첫째 줄에 문제 변환의 과정을 몇 번 거쳤는지를 출력한다. 이 수는 음이 아닌 정수가 되어야 한다. 둘째 줄에는 주어진 수가 3의 배수이면 YES, 아니면 NO를 출력한다.

---

재귀함수를 이용한 문제인데 재귀보다는 큰 수를 처리하는 테크닉이 더 까다로운 문제 같다.

첫 제출 때 런타임 에러가 발생해서 의문이 생겼는데 문제의 조건에서 주어지는 큰 수 X가 1,000,000자리 이하의 수다.

쪼개서 합치기 전까지는 반드시 문자열로 다뤄야 한다는 점.

제출시 NumberFormat 에러가 발생한다면 123456789123 같은 테스트 케이스를 넣어보면 된다.

package baekjoon.free;
import java.io.*;

public class B_1769 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int count = 0; //재귀의 반복 횟수를 담을 static 변수 
    public static void main(String[] args)throws IOException {
        String X = br.readLine(); //큰 수 X를 문자열로 입력 받기
        prob(X);//힘수 호출 
        bw.flush();
        bw.close();
        
    }
    public static void prob(String X) throws IOException {
        String[] data = X.split(""); //큰 수 X를 자릿수로 나눈 배열을 생성
        int sum = 0;//자릿수로 나누고 합친 값을 담을 변수
        if (data.length<2) { //배열의 길이가 2 미만(한 자릿수라면)
            sum = Integer.parseInt(X);//분해합을 구하지 않고 바로 X를 변수에 담는다
        } 
        else {
            count++; //배열의 길이가 2 이상(두 자릿수 이상이라면) 분해합 구하는 횟수에 1을 더하고
            for (int i=0;i<data.length;i++) {
                sum += Integer.parseInt(data[i]); 분해합을 구해서 변수에 담는다
            }
        }
        if (sum>9) {
            prob(Integer.toString(sum)); //분해합이 두 자릿수 이상이라면 재귀 호출 
        }
        else { //분해합이 한 자릿수라면 결과 처리 
            if (sum%3==0 && sum>2) { // 3으로 나눈 나머지가 0이고 3 이상이면(3의 배수) 
                bw.write(Integer.toString(count)); 
                bw.newLine();
                bw.write("YES"); //분해합을 구한 횟수와 YES를 출력 
            }
            else { //분해합이 한 자릿수가 됐을 때 3의 배수가 아니라면
                bw.write(Integer.toString(count)); 
                bw.newLine(); 
                bw.write("NO");  //분해합을 구한 횟수와 NO를 출력
            }
        }
    }  
}