SWEA - 7193. 승현이의 수학공부

pass code는 맨 아래에 있습니다.

 

 

1. 실패코드 (시간초과)

받은 수를  10진수로 변환 -> 그다음 N-1 로 나눈 나머지 값구함..

이게 문제에도 적혀있듯이 X가 매우 큰 숫자임에 유의하라. 때문에 시간 초과가 난다.

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{	
    public static int T,N;
	public static long dec,ans; //10진수
	public static String X;
	public static void main(String args[]) throws Exception
	{
				Scanner sc = new Scanner(System.in);

		
		T = sc.nextInt();
		for (int tc = 0; tc < T; tc++) {
			ans = 0;
			dec= 0;
			N = sc.nextInt();
			X = sc.next();
			
			for (int i = 0; i < X.length(); i++) {
				dec+= Character.getNumericValue(X.charAt(X.length()-1-i)) * Math.pow(N, i);
			}
			
			ans = dec % (N-1);
			
			System.out.println("#"+(tc+1)+" "+ans);
		}
	}
}

 

2.통과코드

구글링해서 본 결과 규칙이 있는것으로 보였다.

페르마의 소정리 기법이라고 한다.

10진수 345라는 값이 있고 N-1인 9로 나눈 나머지를 구할때

(3 + 4 + 5) % 9 한것과  345 % 9 한 것이 같다.

이를 N진수에도 적용하여 계산 한 것..

ex) 9진수 234를 8로 나눈다면

(2 + 3 + 4) % 8 = 1

 

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{	
    public static int T,N;
	public static long dec,ans; //10진수
	public static String X;
	public static void main(String args[]) throws Exception
	{
				Scanner sc = new Scanner(System.in);

		
		T = sc.nextInt();
		for (int tc = 0; tc < T; tc++) {
			ans = 0;
			dec= 0;
			N = sc.nextInt();
			X = sc.next();
			
			for (int i = 0; i < X.length(); i++) {
				dec+= Character.getNumericValue(X.charAt(i));
			}
			ans = dec % (N-1);
			
			System.out.println("#"+(tc+1)+" "+ans);
		}
	}
}