[백준알고리즘] 1629번: 곱셈 -Java

[백준알고리즘] 1629번: 곱셈 -Java
https://www.acmicpc.net/problem/1629

1629번: 곱셈

왜 틀리지 왜 틀리지... 했는데 자료형 때문이었다... 찍어보니 초과해서 -값들이 우수수수 나오는 걸 보고 금방 해결했다 ㅜㅜ 왜 생각하지 못했을까

 

아무튼 이 문제는 분할정복 문제이다. 이 문제를 풀기 위해서는 "빠른 모듈로 거듭제곱 법"을 알아야 한다.

간단하게 설명하자면, 정수 A를 B로 나눈 나머지 A%B는 A mod B로 표현이 가능하다.

이때, (A^2) mod B = (A*A) mod B = ((A mod B) * (A mod B)) mod B 임을 이용하면 된다. 이 식을 이용해 A^N을 B로 나눈 나머지를 빠르게 찾을 수 있으며 logN의 시간 복잡도까지 줄일 수 있다.

또한 이전에 연산했던 값을 중복으로 계산하지 않고 시간을 줄이기 위해서 HashMap을 이용해서 저장해 놓았다.

 

코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;

public class Main1629 {

	static int [] input = new int [3];
	static int value;
	static HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			String [] temp = br.readLine().split("\\s");
			br.close();
			for(int i = 0; i < 3; i++) {
				input[i] = Integer.parseInt(temp[i]);
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
		
		value = (input[0] >= input[2]) ? input[0]%input[2] : input[0];
		long result = solve(input[1]);}
		
		try {
			bw.write(result + "\n");
			bw.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
		
	}
	
	public static long solve(int n) {
		long result = 1L;
		
		if(map.containsKey(n)) {
			return map.get(n);
		}
		
		if(n == 1) {
			result = input[0] % input[2];
		}
		else {
			if(n % 2 == 0) {
				long tmp = solve(n/2);
				result = (tmp * tmp) % input[2];
			}
			else {
				result = (solve(n/2) * solve(n/2 + 1)) % input[2];
			}
		}
		map.put(n, (int) result);
		
		return result;
	}

}

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다