글 읽기 - [나무자르기] 어디서 틀렸는지 모르겠어요...ㅜ

osb1808 5년 전 0

이분탐색 문제인데... 이분탐색으로 했는데

어디서 틀렸는지 모르겠습니다...

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

public class Main {

    private BufferedReader br;
    private StringTokenizer st;
    private int treeNum, length, max=0,min=0,mid;
    private int[] tree;
    public void start() throws IOException
    {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        treeNum = Integer.parseInt(st.nextToken());
        length = Integer.parseInt(st.nextToken());
        tree = new int[treeNum];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<treeNum; i++)
        {
            tree[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, tree[i]);
        }
        mid = max / 2;
        changeMax(max, mid, min);
    }
    private void changeMax(int max,int mid,int min)
    {
       // System.out.println("max : " + max + " mid : " + mid + " min : " + min);
        int temp = check(mid);
        if(mid == max || mid == min)
        {
            System.out.println(mid);
            return ;
        }
        if(temp > length)
        {
            changeMax(max,(max+mid)/2,mid);
        }
        else if(temp < length)
        {
            changeMax(mid,(min+mid)/2,min);
        }
        else
        {
            //temp == length
            System.out.println(mid);
            return ;
        }
    }
    private int check(int heigth)
    {
        int total =0;
        for(int i=0; i<treeNum; i++)
        {
            if(tree[i] > heigth)
            {
                total += tree[i] - heigth;
            }
        }
        //System.out.println("total의 값 ::" + total);
        return total;
    }
    public static void main(String[] args) throws IOException
    {
        new Main().start();
    }
}

djm03178 5년 전 2

단순히 int로 계산하면 오버플로가 발생합니다.

5 2000000000
1000000000 1000000000 1000000000 1000000000 1000000000

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

문제

문제

출처

ICPC

[나무자르기] 어디서 틀렸는지 모르겠어요...ㅜ

osb1808 5년 전 0

djm03178 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말