백준 1629번 (java)

접근

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

이 문제는 몇 가지만 주의하면 아주 쉬운 문제이다.

• 매 연산의 결과가 overflow가 발생하지 않도록 주의할 것
• 0.5초의 제한 시간이 있으므로 연산횟수가 10억 이상을 넘어가지 않도록 할것

따라서 문제 자체에서도 overflow가 발생되지 않도록 C라는 값을 입력값으로 받아 매 연산마다 C로 나눈 나머지를 출력할 것을 요구하고 있다.

입력값들은 2,147,483,647 이하의 자연수 즉, int 자료형에 딱 맞는 범위만을 가지고 있는 자연수이다.

과정

연산의 횟수를 줄이기 위해서 재귀함수를 이용한다.

A의 4승은 A의 2승을 2번 곱한 것이다.

이 성질을 이용해서 연산의 횟수를 줄이도록 한다.

  static long make(int A, int B, int C){
        if(B==1){
            return A%C;
        }

        long sub =make(A,B/2,C);
        sub = (sub *sub)%C;
        if(B%2!=0){
            sub =(sub*A)%C;
        }
        return sub;

    }

따라서 재귀함수는 위와 같다.

또한 sub=(sub *sub)%C를 하는 과정에서 sub*sub가 int의범위를 넘어갈 수도 있으므로 더 큰 정수형 자료형인 long으로 sub를 선언한다.

기억하기
연산 결과뿐만 아니라 연산 하나에서도 자료형을 고려해야 한다.
https://www.acmicpc.net/board/view/20940

풀이 (java)

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        //System.out.println(A+","+B+","+C);

        // 중요 0.5초 연산이 5억이상을 넘어서서는 안된다.
        // 각 주어지는 수는 2,147,483,647 이하의 자연수


        long answer = make(A,B,C);
        bw.write(Long.toString(answer));
        bw.flush();
        bw.close();
        br.close();



    }

    static long make(int A, int B, int C){
        if(B==1){
            return A%C;
        }

        long sub =make(A,B/2,C);
        sub = (sub *sub)%C;
        if(B%2!=0){
            sub =(sub*A)%C;
        }
        return sub;

    }
}