글 읽기 - 제가 한게 이분탐색이 맞나요...?

fbcks97 2년 전 0

그냥 DP적인 풀이에다가 값을 하나씩 for문으로 하면서 풀었는데 통과가 되네요.... 이게 이분탐색이 맞나요?

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int H = sc.nextInt();
        
        int haveTo = Integer.MAX_VALUE;
        int haveToCnt = 0;
        
        int up_cnt[] = new int[H+1];
        int un_cnt[] = new int[H+1];
        
        for(int i=0; i<N; i++){
          if(i%2==1) up_cnt[sc.nextInt()]++;
          else un_cnt[sc.nextInt()]++;
        } 
        
        for(int i=H-1; i>0; i--){
            up_cnt[i] += up_cnt[i+1];
            un_cnt[i] += un_cnt[i+1];
        }
        
        for(int i=1; i<H+1; i++){
            int brake = up_cnt[i] + un_cnt[H-i+1];
            if(brake < haveTo){
                haveTo = brake;
                haveToCnt = 1;
            }else if(brake == haveTo) haveToCnt++;
            
        }
        System.out.println(haveTo);
        System.out.println(haveToCnt);
        
    }
}

lcr7324 2년 전 0

아니오

fbcks97 2년 전 0

아 제방식은 누적합이군요...

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

문제

문제

출처

ICPC

제가 한게 이분탐색이 맞나요...?

fbcks97 2년 전 0

lcr7324 2년 전 0

fbcks97 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말