글 읽기 - 안녕하세요 이분탐색으로 풀었는데, 틀린 이유를 알수가 없어서 질문 드립니다.

idjjm92 3년 전 0

안녕하세요, 자바 고수님들, 제가 이분탐색으로 이문제를 풀려고 해보았습니다,

그런데 출력은 맞는 것 같은데, 채점서버에서는 계속 오답이라는 메시지를 얻고 있네요,

질문게시판에서 여러가지 반례들을 확인해서 올려봤지만,

특이한점을 찾기가 어려워서, 질문 올립니다.

시간내주셔서 고맙습니다~

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

// 시도한 반례 리스트
/**
 * 4 7
 * 20 15 10 17
 */


/**
 * 6 25
 * 20 15 10 16 41 44
 */

/**
 * 1 10
 * 17
 */

/**
 * 1 9
 * 17
 */

/**
 * 20 1000000000
 * 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1000000000
 */

/**
 * 6 1
 * 0 2 0 0 0 2
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] token = bf.readLine().split(" ");

        long[] inputs = new long[token.length];
        for (int i = 0; i < token.length; i++) {
            inputs[i] = Integer.parseInt(token[i]);
        }
        ;

        String[] treesToken = bf.readLine().split(" ");
        long[] trees = new long[treesToken.length];
        for (int i = 0; i < treesToken.length; i++) {
            trees[i] = Integer.parseInt(treesToken[i]);
        }
        // bf 종료
        bf.close(); // ------ 입력
        
        // 알고리즘 풀이
        boolean isLack = true;
        
        // 탐색 시작점은 0으로, 합니다. 
        long start = 0; 
        
        // 나무 최대 크기가 10억이기 때문에, 마지막 탐색지점은 10억으로
        long end = 1000000000; 
        
        // 2진탐색으로 풀었기 떄문에, 탐색지점을 중간부터 시작해 줍니다.
        long cutSize = (start + end) / 2; 
        
        // amount는 잘라서 가지고 갈 나무들의 총 길이 입니다.
        int amount = 0;
        
        // need 는 필요한 나무의 길이 입니다.
        long need = inputs[1];
        
        // 탐색하려고 하는 해를 찾으면 isLack 를 true로 바꿔서 루프를 중단시킵니다.
        while (isLack) {
            // 종료 조건을, start 와 (start+end)/2 가 같아지는 지점으로 잡았습니다. int형이기 떄문에 end-start = 1이라면, cutSize = start 는 같게 됩니다.
            if (start == cutSize) {
                isLack = false;
            }
            
            /* 나무를 잘라서 자른 나무의 총합을 구하는 코드 입니다. */
            // 자른 나무들을 다 더한다. amount 를 루프가 돌기 직전 0으로 초기화 해줍니다.
            amount = 0;
            for (int i = 0; i < trees.length; i++) { 
                if (trees[i] - cutSize <= 0) {
                    // 칼 사이즈보다 나무가 작아서 잘리지 않을 경우 입니다.

                } else {
                    
                    // 자르고 남은 사이즈를 amount 에 더해줍니다.
                    amount += trees[i] - cutSize;
                }
            }

            /* 자른 나무의 총합을 가지고, 이분탐색의 범위를 조정하는 코드. */
            if (amount > need) { 
                
                // 칼 사이즈를 크게 한다.
                start = cutSize;
                cutSize = (start + end) / 2;
            } else if (amount == need) {
                
                // 필요한 만큼의 수량을 딱 찾아내게 되면, 탐색을 종료합니다.
                isLack = false;
            } else {
                
                end = cutSize;
                cutSize = (start + end) / 2;
            }
        };
        System.out.println(cutSize);
    }
}

slah007 3년 전 1

68줄 amount의 자료형을 long으로 해야 할 것 같습니다.

idjjm92 3년 전 0

고맙습니다 :) 덕분에 해결되었어요~~ 고맙습니다~

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

문제

문제

출처

ICPC

안녕하세요 이분탐색으로 풀었는데, 틀린 이유를 알수가 없어서 질문 드립니다.

idjjm92 3년 전 0

slah007 3년 전 1

idjjm92 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말