[java][boj][s1] 1629. 곱셈

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

1629번: 곱셈

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

풀이

/*
 * 입력
 * 1. A B C
 * 출력
 * 1. A를 B 번 곱한 수 이를 C로 나눈 나머지
 * 
 * >> B를 반으로 계속 쪼개서 1이 나오면 계산
 * >> A를 C로 나눠서 나머지를 계산
 */

재귀를 이용해서 B가 1이 될 때까지 분할한 뒤 하나씩 곱해 나가는 방식으로 구했다 C로 나눈 나머지로 구해야 하기 때문에 계속해서 나눠서 곱해 줬더니 오류가 났다 알고 보니 나눈 뒤 곱하는 게 아니라 곱한 뒤 나머지로 나눠야 그 값이 구해진다 왜 안 되는 건지는 잘 모르겠지만... 틀린 부분은 주석 처리했다

코드

package lv20_분할정복;

import java.util.*;
import java.io.*;

public class s1_1629_곱셈 {
	static long A, B, C;
	static long ans;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		A = Long.parseLong(st.nextToken());
		B = Long.parseLong(st.nextToken());
		C = Long.parseLong(st.nextToken());
		
		ans = pow(A%C, B);
		
		System.out.println(ans%C);
	}

	private static long pow(long a, long b) {
		System.out.println("리턴" + b);
		//b가 0일 때 1 리턴
		if(b==0) return 1;
		//b가 1일 때 a 리턴
		if(b==1L) return a;
		
		ans = pow(a, b/2);
		System.out.println("리턴" + b);
		//ans = ans%C * ans%C;
		ans = ans*ans%C;
		
		//b가 홀수일 경우 a를 한 번 더 곱해 줌
		//if(b%2==1L) ans *= A%C;
		if(b%2==1L) ans *= A;
		
		//return ans;
		return ans%C;
	}

}

결과

 

#자바 #java #boj #백준 #알고리즘