글 읽기 - Good Bye BOJ 2021 B번 문제 JAVA

wnsgh745896 2년 전 0

B 케이크 문제입니다

구현한 방법은 부피가 N이고 높이 1 가로 a 세로 b라고 했을때

for문으로 k=1을 N의 루트번 돌리고

k가 N의 배수일때

k가 a+b가 3의 배수 일때는 TAK

아닐떄는 NIE를 출력하게 만들었습니다

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

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));        
        
        int T = Integer.parseInt(br.readLine());
        
        
        for (int i = 0; i < T; i++) {
            
        Long N = Long.parseLong(br.readLine());
        
            boolean isCake = false;
                                    
            double multiMax = Math.sqrt(N);
            
            for(int k = 1; k <= multiMax; k++) {
                
                if (N % k == 0) {
                    double ab = k + (N/k);
                    if (ab%3 == 0) {
                        isCake = true;
                        break;
                    }
                    
                }
            }        

            if (isCake)
                bw.write("TAK\n");
            else
                bw.write("NIE\n");

            bw.flush();
        }
        
        
        bw.close();
    }

    
}

shjohw12 2년 전 0

이렇게 풀면 시간복잡도가 O(T * sqrt(N)) 이라서 제한 시간 내에 해결할 수 없습니다. 다른 방향으로 생각해보셔야 합니다.

wnsgh745896 2년 전 0

당시에 시간 초과가 안 나오고 틀렸다고 나왔는데 혹시 시간 초과인데 틀렸다고 나올수있나요?

shjohw12 2년 전 2

시간 초과 데이터 전에 틀리는 데이터가 먼저 나와서 그렇습니다. 즉 제한 시간 내에 해결할 수도 없고, 답도 잘못 내는 풀이라는 뜻입니다.

wnsgh745896 2년 전 0

감사합니다 궁금증이 해결된거 같습니다

저 코드에서 28번줄 double ab = k + (N/k); 에서 오차범위 때문에 먼저 틀리고 시간초과 안난 것은 오차범위때문에 먼저틀려서 안난거네요

아직 8일차라서 그런지 틀렸다고 나오자 시간초과는 안되는지 알았어요 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

Good Bye BOJ 2021 B번 문제 JAVA

wnsgh745896 2년 전 0

shjohw12 2년 전 0

wnsgh745896 2년 전 0

shjohw12 2년 전 2

wnsgh745896 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말