[ 백준 1629 ] 곱셈 - Java

문제 링크

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

1629번: 곱셈

문제 풀이

해당 문제는 A의 B제곱을 구해서 C로 나눈 나머지를 구하는 문제입니다.

얼핏 보면 간단해 보이는 문제이지만 범위가 굉장히 크죠 A, B, C 모두 2,147,483,647 이하의 자연수입니다.

그래서 만약 A의 2,147,483,647 제곱을 구하려면 많은 연산이 필요하고, 시간 복잡도가 올라가게 됩니다.

 

그럼 이 문제를 어떻게 풀어야 할까요??

분할 정복과 DP로 풀면 되는데, 다음에 나오는 예를 같이 보며 이해해보겠습니다.

 

예를 들어 A의 1024 제곱을 13으로 나눈 나머지를 구한다고 생각해봅시다.

단순하게 반복문으로 A의 1024제곱을 구하려면 1024번을 반복해야 됩니다.

하지만 A ^ 512를 구해서 그 수를 제곱하면 시간이 반으로 줄겠죠.

그런데 계속해서 반복해나간다면 A가 1024개로 쪼개지기 때문에 의미가 없어집니다!!

 

여기서 필요 한것이 DP입니다.

우선, A의 1024를 A(1024)로 표현해보겠습니다. 

그렇다면 A는 계속해서 쪼개보면 A(512) , A(256) ... 쪼개지겠죠.

그럼 A(512)는 A(1)을 512번 호출합니다.

A(512) * A(512)이면 각 512번 + 512번인데 첫 A(512)를 계산하면서 이미 값을 알게 되겠죠.두번째 A(512)를 구하지 않기 위해서 A(512)값을 배열에 저장해 놓고, 두번째A(512)값은 배열에서 꺼내와서 계산하게 되면 굉장히 효율성이 올라값니다.

 

 

 

이 로직을 top-down 방식의 DP로 구현하면 다음과 같은 코드가 나오게 됩니다.

 

 

소스 코드

import java.util.*;

public class Main {
	static long A ;
	static long C ;
	static HashMap<Long , Long> memo;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		A = sc.nextInt();
		int B = sc.nextInt();
		C = sc.nextInt();
		memo = new HashMap<>();
		Long ans = sol(B);
		System.out.println(ans);

	}

	public static long sol(long b) {
		if(memo.get(b) !=null) return memo.get(b);
		if(b==1) memo.put(b, A%C);
		else if(b %2 ==0)  memo.put(b,sol(b/2) * sol(b/2) % C);
		else  memo.put(b, ((sol(b/2) * sol(b/2)  % C) * sol(1))%C);

		return	memo.get(b);
	}
}