boj 6236

문제 풀이

문제를 보면 인출 횟수가 5가 되겠끔 맞추는 문제이다
즉 500을 보면
100 400 ->1
300 1000 -> 2
500 -> 3
101 -> 4
400 -> 5

가 되는 문제이다
즉 해당 돈이 500이 되면 count 를 올리는 것인데 이거에 반대
count 가 5가 되는 것을 찾는 문제이다

count 가 5가 되려고 찾을 수 있는 방법은 배열에서 가장 큰 동전 (현재는 500) 이유는 가장 큰 동전으로 해야지 모든 동전을 맞게 사용 가능 그리고 제일 큰 돈 모든 배열 합 (1901) 을 for 문을 돌려 찾는 것이다

현대 이것을 for 문을 비교해서 찾으면 언제 다 찾느냐 그래서 이분탐색을 선택하였다

첫번째(500) 과 마지막(1901) 을 아니 중간 (1200) 을 하여 1200 시 인출 경우 (2) 니 end = mid 로 보내는 방식 만약 크거나 같을시 start = mid+1 방식 사용 하였다 (lower바운드 )

전체 코드

  public static  void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] arr = new int[n];
        int end =0;
        int start = 0;
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(br.readLine());
            if(arr[i] > start){
                start = arr[i];
            }
            end += arr[i];
        }

        while(start < end){
            int mid = (start+end)/2;
            int sum = 1;
            int a = mid;
            System.out.println(start + " " + end);
            System.out.println(mid);
            for(int i=0; i<n; i++){
                System.out.println(a + "dd");
                System.out.println(sum);
                if(a<arr[i]){
                    sum ++;
                    a = mid;
                    a-= arr[i];
                }else{
                    a -= arr[i];
                }
            }
            System.out.println(sum + "sum");

            if(sum <= m){
                end = mid;
            }else{
                start = mid+1;
            }
        }
        System.out.println(end);

    }