[백준] 단계별로 풀어보기(단계:20,분할 정복,JAVA)1629번, 곱셈

문제 링크

1629번: 곱셈

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

분할 정복 알고리즘은 일정한 간격으로 입력된 값을 분할하여 조건에 맞는지 확인하고 틀리면 다시 일정한 간격으로 분할하는 것을 반복하여 조건에 만족할 때까지 진행하는 알고리즘입니다.

 

처음에 문제를 접근할 때에는 분할정복을 사용하지 않고 나머지를 구할 때에 반복하는 구간을 찾고 그 구간을 토대로 나머지를 구하는 방식을 사용해보았습니다.

하지만 결과는 제대로 나오지만 "메모리 부족"이라는 상태로 실패하였습니다. 그래서 구글링을 통해 모듈러 산술을 알게 되었고 모듈러 연산과 분할 정복을 이용하여 문제를 해결하였습니다.

 

모듈러 산술이란?( n mod m = n을 m으로 나누었을 때 나머지라는 뜻입니다.)

(a+b) mod p = (a mod p + b mod p) mod p

(a-b) mod p = (a mod p - b mod p) mod p

(a*b) mod p = (a mod p * b mod p) mod p

이 공식은 나머지를 구하는 것도 결합/교환 법칙이 적용된다는 것을 보여주는 것입니다.

자세한 공식의 설명은 제가 참고한 사이트의 링크를 참고해주시면 감사하겠습니다.

모듈러 산술 - 위키백과, 우리 모두의 백과사전

 

ko.wikipedia.org

알고리즘을 살펴보기 이전에 예제입력을 먼저 살펴보도록 하겠습니다.

예제입력을 식으로 나타내면 

위와 같이 계수를 제곱형태로 바꿀 수 있으며 위 식을 모듈러 산술로 표현할 수 있습니다.

위처럼 10ⁿ의 형태를 계속 제곱의 형태로 바꾸면 n=1이 상황이 오면 10 mod 12 = 10이 됩니다.

위 과정을 재귀하여 값을 받아오고 나머지를 구하는 과정을 반복하면 모듈러 산술연산을 반복하는 것과 동일한 효과를 받을 수 있습니다.

 

이제 해결 알고리즘을 살펴보면

1. 입력값을 제곱의 형태로 만들기 위해 B/2를 합니다.

2. B가 홀수이면 Aⁿ * A형태에서 (Aⁿ)² * A의 형태로 만들어 모듈러 산술처럼 나머지를 구해줍니다.

3. B가 짝수이면 Aⁿ 형태에서 모듈러 산술처럼 나머지를 구해줍니다.

4. B가 1이 될 때까지 재귀하면 나머지 값은 A % C가 됩니다.

5. 재귀를 다시 돌아오면서 나머지 연산을 반복하여 입력받은 B만큼 되었을 때 나머지를 구해서 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 사용하여 띄어쓰기 기준으로 A, B, C를 저장하였습니다.
• 곱셈의 나머지를 구하는 mul함수를 만들었습니다.
• 함수를 실행 후 BufferedWriter에 연산의 결과를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• mul함수에서 if문을 사용하여 B가 1일 때 결과를 반환하도록 하였습니다.
• mul함수에서 temp에 제곱의 형태로 변경하여 연산을 진행하도록 재귀를 진행하였습니다.
• mul함수에서 if문을 통해서 B가 홀수일 때와 짝수일 때에 모듈러 산술을 알맞게 적용하도록 하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static long result;	//결과 변수
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값을 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값을 출력하는 BufferedWriter
        //---------입력값 저장---------------
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        long A = Integer.parseInt(st.nextToken());
        long B = Integer.parseInt(st.nextToken());
        long C = Integer.parseInt(st.nextToken());
        result = mul(A, B, C);	//함수 실행
        bw.write(result + "\n");	//결과 BufferedWriter에 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //-----------곱셈 함수------------
    public static long mul(long A, long B, long C) {
    	if(B==1)
    		return A%C;
    	
    	long temp = mul(A, B/2, C);
    	
    	if(B%2==0)		//계수가 짝수일 때
    		return temp * temp % C;
    	else			//계수가 홀수 일 때
    		return (temp*temp%C) * (A%C) % C;
    	
    }
}