글 읽기 - [java] 1629 곱셈 수정 부탁드립니다.

alreadyj 6년 전 0

입력 속도, 출력 속도가 떨어지지 않도록 Scanner를 쓰지 않고 BufferedReader, writer를 사용했어요

아래와 같은 코드를 C++에서 같은 로직으로 작성하였을 시, 무사히 통과하는 모습을 보였습니다.

java에서 TLE가 나는 것은 문제가 있다고 봅니다. 수정 바랍니다

import java.io.*;

public class B1629 {
    static int A, B, C;
    static String ins[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        ins = br.readLine().split(" ");
        A = Integer.parseInt(ins[0]);
        B = Integer.parseInt(ins[1]);
        C = Integer.parseInt(ins[2]);
        bw.write(pow(B) + "\n");
        bw.flush();bw.close();
    }

    public static long pow(int b) {
        if (b == 1) return A % C;
        long ans = pow(b >> 1) * pow(b >> 1);
        ans %= C;
        if (b % 2 != 0) {
            ans *= A;ans %= C;
        }
        return ans;
    }
}

jh05013 6년 전 0

직접 2147483647 2147483647 2147483647을 넣었더니 시간 내에 답이 안 나옵니다. 어디엔가 잘못 짠 부분이 있는 게 아닐까요?

djm03178 6년 전 0

좀 기이한 현상이기는 한데, 이 코드나 C++로 정답을 받으신 코드나 로직으로 봤을 땐 똑같이 시간 초과가 나야 합니다. VS 2017에서도 돌려봤지만

1 1000000000 1

과 같은 케이스에서 많은 시간이 걸립니다. 왜 채점 환경에서는 이것이 0ms가 되는지는, 알아보고 다시 답글을 달겠습니다.

jh05013 6년 전 0

C++ 코드는 잘 돌아가는 것 같던데요.

https://ideone.com/PoPJoY

djm03178 6년 전 0

그게 ideone과 채점 환경은 유사하기 때문에 잘 돌아가는 것 같습니다만, Visual Studio에 넣어봤을 때는 매우 오랜 시간이 걸립니다.

djm03178 6년 전 0

지금 새로 바꾼 노트북에 아직 우분투를 안 깔아서 설치하는 중인데, 일단 로직으로 설명을 해 보자면요,

예를 들어 2^30제곱이 B에 들어왔다면, 2^29을 2번 호출할 테고, 각각이 2^28을 2번 호출하니 총 4번 호출되고, 2^27은 8번 호출되고, ... 2^0은 2^30번 호출될 테니 시간 초과가 나는 게 어찌 보면 당연합니다. 그런데도 시간 초과가 안 나는 건, 컴파일러가 뭔가 손을 썼다고 생각되는데, 한 번 테스트를 해보려고 합니다.