백준 JAVA 1629 곱셈

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

1629번: 곱셈

 

거의 한시간 반동안 잡고있었는데, 못풀어서 다른 블로그의 도움을 받았다.

모듈러 연산과 재귀를 이용해야 하는문제였고, 코드만 보니 이해가 안가서 몇개의 예제를 만들어서 하나하나 분석하니 이해가 됐다. 

3~4일 정도 지나고 다시 트라이 해봐야겠다.

 

 

가장 중요한 로직이다.

cal 메서드를 만들었는데, 결론은 모듈러 연산을 이용한 코드이다.

b 만큼 제곱해야하므로, 2로  b == 0 or b== 1 때까지 나누어야 한다.

또한, b가 짝수일때, 홀수일때를 나누어야 한다.

생각해보면 당연하다. 홀수면 한번 더 곱해줘야하기 때문에.

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);
        return (n * n) % c;

    } else if (b % 2 == 1) {
        long n = cal(a, b / 2, c);
        return (((n * n) % c) * a) % c;

    }

 

출력할때도 헤맸다.

질문검색을 해보니, 똑같은 분이 계셔서 반례를 받았는데 무려 8 따봉을 받은 것보니 비슷한 경우가 많았나보다.

이를 해결하기 위해서는 % c를 한번 더 해줘야한다.

%c 를 2번 하든 3번하든 결과는 똑같다.

System.out.println(cal(a, b, c) % c);

 

package BEAKJOON.silver;
/**
 * 시간 제한   메모리 제한 제출 정답 맞힌 사람  정답 비율
 *  0.5 초 (추가 시간 없음)   128 MB 72063  19518  14362  26.288%
 */

import java.util.Scanner;

public class _1629 {
    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);
    }

    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);
            return (n * n) % c;

        } else if (b % 2 == 1) {
            long n = cal(a, b / 2, c);
            return (((n * n) % c) * a) % c;

        }
        return a;
    }
}

 

 

참고

https://youngest-programming.tistory.com/407

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