[백준] 1629 곱셈, Go/Java

0. 들어가면서

곱셈 문제이다.
재귀 문제이다.

1. Java

1.1 내가 푼 코드

package bj.ch11_recursion;

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

public class BJ_1629_01 {
    static int A, B, C;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        long result = pow(A, B, C);
        System.out.println(result);
    }

    private static long pow(int a, int b, int c) {
        if (b == 1) {
            return a % c;
        }
        long nextV = a * pow(a, b - 1, c);
        return nextV % c;
    }
}

1.2 바킹독 참고한 코드

package bj.ch11_recursion;

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

public class BJ_1629_02_BarkingDog {
    static int A, B, C;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        System.out.println(pow(A, B, C));
    }

    private static long pow(int a, int b, int c) { // a^b mod c = (a^(b/2) mod c * a^(b/2) mod c) mod c
        if (b == 1) {
            return a % c;
        }
        long val = pow(a, b / 2, c);
        val = val * val % c; // a^b mod c = (a^(b/2) mod c * a^(b/2) mod c) mod c
        if (b % 2 == 0) { // 짝수면 그대로
            return val;
        }
        return val * a % c; // 홀수면 한번 더 a, mod c 해줘야지
    }
}

1.3 해설

• 처음에 풀었을 때는 메모리 초과가 났다.
• k, k+1의 귀납적으로 접근을 했더니 너무 많은 메모리가 필요했다.
• 이에 따라, 바킹독의 코드를 참고하여 k일 때, 2k, 2k+1 로 접근을 하니까 메모리 초과가 나지 않았다.

2. Go

CLOSING

재귀를 진행할 떄 순차적 접근도 좋지만 이진트리 같은 형식의 접근은 없는지 항상 다양하게 생각해보자!