250x250
Notice
12-08 02:11
관리 메뉴

막내의 막무가내 프로그래밍 & 일상

[알고리즘] 백준 1629 곱셈 - 분할정복- 자바 본문

알고리즘/분할정복

[알고리즘] 백준 1629 곱셈 - 분할정복- 자바

막무가내막내 2020. 10. 18. 21:09
728x90

www.acmicpc.net/problem/1629

 

1629번: 곱셈

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

www.acmicpc.net

 

 

백준 분할정복 단계별풀기 네번째 곱셈 문제를 풀어봤습니다.

처음 단순하게 곱하고 나눠주고 반복문 돌렸다가 시간복잡도 때문에 시간초과가 났습니다. 

분할정복 단계므로 분할해서 재귀를 사용해 풀었습니다.

 

밑 공식대로 풀면 됩니다.

 

출처 : https://onsil-thegreenhouse.github.io/programming/problem/2018/03/29/problem_math_power/

 

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long A = sc.nextLong(); //밑
        long B = sc.nextLong(); //지수
        long C = sc.nextLong();
        System.out.println(cal(A, B, C) % C);
    }

    private static long cal(long a, long b, long c) {
        if (b == 0) {
            return 1;
        } else if (b == 1) {
            return a;
        } else if (b % 2 == 0) { //짝수 지수
            long n = cal(a, b / 2, c) % c;
            return (n * n) % c;
        } else { //홀수 지수
            long n = cal(a, b / 2, c) % c;
            return (((n * n) % c) * a) % c;
        }
    }
}

 

 

 

참고 : onsil-thegreenhouse.github.io/programming/problem/2018/03/29/problem_math_power/

 

[Problem] 어떤 수의 n제곱 구하기(백준 1629번) - Onsil's blog

초짜 개발자 온실의
스터디 블로그

onsil-thegreenhouse.github.io

 

728x90
0 Comments
댓글쓰기 폼