BAEKJOON / 백준 - JAVA 31738번 매우 어려운 문제

2024.04.23 기준 - 실버5

 

문제

입력

출력

제한

예제

입력	출력
5 7	1

 

백준, BEAKJOON, BOJ, JAVA, 자바

 

 

풀이

이 문제는 전부 다 계산을 하면 시간초과가 나는 문제입니다.

풀이 방법은 매우 간단합니다.

예를 들어 n은 5, m은 7이라고 가정을 하겠습니다.

5! = 5 x 4 x 3 x 2 x 1 = 120

120에 7을 나눈 나머지는 1이 됩니다.

 

하지만 n이 커질수록 계산 속도가 느려집니다.

만약, n이 500000, m이 12345라고 가정을 하겠습니다.

500000! = 500000 x 499999 x 499998 x ... x 12345 x ... x 1이 됩니다.

 n이 m보다 클 경우,

무조건 m이라는 값을 곱해야 되기 때문에 n!은 m의 배수가 될 수 밖에 없습니다.

따라서 나머지는 무조건 0이 됩니다.

 

즉, n >= m 이 되면 답은 무조건 0이 됩니다.

이제 남은 경우는 n < m인데 이 값은 m의 최대값은 10^7이기 때문에 시간 내에 통과가 가능해집니다.

 

풀이 코드

public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		long n = Long.parseLong(st.nextToken());
		long m = Long.parseLong(st.nextToken());
		long result = 1;
		
		// m이 n보다 작거나 같은 경우 result는 무조건 0이다.
		if (m <= n) { 
			result = 0;
			
		} else {
			for (long i = n; i > 0; i--) {
				result *= i;
				result %= m;
				
				// result가 0에서 무슨 값을 곱해도 result는 0이기 때문에 break. 
				if (result == 0) { 
					break;
				}
			}
		}
		
		bw.write(Long.toString(result));
		bw.flush();
		bw.close();
		br.close();
	}

 

 

잘못된 정보는 댓글로 알려주시면 감사하겠습니다.