[JAVA][SWEA] 7193. 승현이의 수학공부

승현이는 N(2 ≤ N ≤ 10) 진법의 수 X(1 ≤ X ≤ N^10,000,000) 를 공책에 적었다.

승현이는 손이 점점 아프기 시작했고, 머릿속에서 문득 X를 (N-1)로 나눈 나머지가 궁금해졌다.

승현이를 도와 N진법의 수 X가 주어졌을 때에 X를 (N-1)로 나눈 나머지를 계산하는 프로그램을 작성하라.

예를 들면, 9진법의 수 234는 10진법으로 193이고, 8로 나눈 나머지는 1이 된다.

 

이 문제에서 정말 편하게 생각하면 주어진 수를 10진법으로 바꾸고 (N-1)을 % 연산하면 나머지가 구해지지 않나? 라고 생각할 수 있지만 N이 10,000,000이라는 것에 주목해야 한다.

 

java의 경우 Integer.parseInt( '숫자', '진법' ) 을 하게 되면 알아서 숫자가 진법 변환되어 값이 나온다.

예를 들어, Integer.parseInt( 234, 9 ) 를 하게 되면 193이라는 수가 반환 된다. 

 

하지만 최대 값을 생각 하였을때 10진법수 10^10,000,000의 경우 너무 큰 숫자이기에 연산하는 것이 불가능 하다.

 

이를 위해 최소한의 연산을 하여야 하는데

방법은 다음과 같다.

 

예를 들어, 10진 법수 2345 가 있다고 가정하고 이를 9로 나눈 수의 나머지를 구하고 싶을 때 실제 계산 값은 9 이다.

하지만 잘 뜯어 보았을때 ( 2 + 3 + 4 + 5 ) % 9 인 것을 확인 할 수 있는데

이를 이용하여 결과적으로 자리수를 다 더한뒤 % 9를 하면 된다.

 

10진수라서 그렇다고 생각하시는 분들을 위해 본문의 예시인 9진법 수 234의 경우

2 + 3 + 4는 9가 되고 % 8 은 1이 된다.

 

마지막 예시는 5진수 14231 을 예로 들면 4로 나누었을때 3이 나오는데

1 + 4 + 2 + 3 + 1 은 11 이고 4로 나누면 3이 나온다.

 

이 논리는 페르마의 소정리를 이용하는 것으로 기억하고 있는데 이 부분에 대해서는 자세히 설명하고 있는 다른 페이지를 참고 하는 것을 추천한다.

 

결과적으로 총 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Solution {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());
		String[] s = null;
		int N = 0;
		String str = "";
        int sum = 0;
		for(int t=1;t<=T; t++) {
			s = br.readLine().split(" ");
			N = Integer.parseInt(s[0]);
			str = s[1];
			sum = 0;
			for(int i=0; i<str.length(); i++) {
				sum += Integer.parseInt(str.substring(i, i+1));
			}
			bw.write("#"+t+" "+(sum%(N-1))+"\n");
		}
		br.close();
		bw.close();
	}
}