글 읽기 - java11 - 매개변수 탐색 질문입니다

eksrks0310 2년 전 0

안녕하세요 자바로 매개변수 탐색을 써봤는데 어느 부분을 고쳐야 할지 도저히 모르겠습니다...

long 범위 생각해서 예외처리도 최대한 해보았는데 큰 수를 아무리 넣어봐도 틀린 케이스를 모르겠네요..ㅠㅠ

아직 초보라 코드가 상당히 더러울텐데 최대한 주석처리 해봤습니다ㅠ

import java.util.*;
import java.io.*;

public class Main {
    static HashMap<Integer, Integer> emap = new HashMap<>();
    static HashMap<Integer, Integer> nmap = new HashMap<>();
    // emap : 무조건 넣어야하는 재료를 (부패속도 s : 유통기한 l)의 맵으로 저장
    // namp : 빼도 되는 재료를 위처럼 저장
    static PriorityQueue<Long> prior;
    static int K;
    static int G;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        G = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        for (int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int l = Integer.parseInt(st.nextToken());
            if (st.nextToken().equals("0")){
                emap.put(s, l);
            }
            else{
                nmap.put(s, l);
            }
        }

        int start = 0;
        int end = 2 * (int)Math.pow(10, 9);
        // parametric search
        while (start + 1 < end){
            int mid = (start + end) / 2;
            prior = new PriorityQueue<>(Collections.reverseOrder());
            // 세균수의 우선순위 큐(우선순위 큰 것부터 - reverseOrder)
            for (Integer i : nmap.keySet()){
                prior.add((long)i * (long)Math.max(1, mid - nmap.get(i)));
            }
            for (int i = 0; i < K; i++){
                prior.poll();
            }
            // 빼도 되는 재료에서는 세균수가 가장 큰 k개의 케이스를 빼야함
    
            for (Integer i : emap.keySet()){
                prior.add((long)i * (long)(Math.max(1, mid - emap.get(i))));
            }

            if (check()){
                start = mid;
            }
            else{
                end = mid;
            }
        }

        bw.write(String.valueOf(start));
        
        bw.flush();
        bw.close();
    }

    public static boolean check(){
        // mid일이 지났을 때 먹을 수 있을지 체크
        long sum = 0;
        // 세균수의 합
        int size = prior.size();
        for (int i = 0; i < size; i++){
            long temp = prior.poll();
            if (temp > G){
                return false;
            }
            // 유통기한이 0, 날짜가 1e9, 부패속도가 1e9이면, 모두 더하다가 long 범위를 넘어갈것 같아서 조건문 추가
            sum += temp;
        }

        if (sum < G){
            return true;
        }
        else{
            return false;
        }
    }
}

floatingice 2년 전 1

해시맵은 키, 값 형태로 값을 저장하는데, 값을 저장할 때 기존에 같은 키 값이 있으면 새로 추가하는 대신 기존의 값을 변경해요.

문제의 조건을 보면 s가 같은 재료가 있을 수도 있는데, 이 경우 기존의 재료 정보가 덮어씌워지면서 날아가요.

이 부분 때문에 오답이 나오는 것 아닐까요?

+ 문제의 조건을 보면 세균 수가 G "이하"면 그냥 먹기로 되어있어요. 그러니 80번째 줄을 sum <= G로 바꿔야해요.

eksrks0310 2년 전 0

와 부패속도가 같은 경우는 생각도 못했네요 ㅠㅠㅠ

자료형을 바꿔서 다시 해보겠습니다 감사합니다!!!

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

문제

문제

출처

ICPC

java11 - 매개변수 탐색 질문입니다

eksrks0310 2년 전 0

floatingice 2년 전 1

eksrks0310 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말