글 읽기 - 반례를 찾습니다 ㅠ

tjdgur23 3년 전 0

제출하면 1%에서 틀려버리는데,

아무리 생각해봐도 떠오르는 반례가 없네요 ㅠㅠㅠ

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

public class Baek18111 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		Map<Integer, Integer> hsmap = new HashMap<>();

		int[][] arr = new int[N][M];
		for (int i = 0; i < arr.length; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < arr[i].length; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				hsmap.put(arr[i][j], hsmap.getOrDefault(arr[i][j], 0) + 1); // 같은 높이의 블럭들의 개수를 (key:높이 value:;개수) 쌍으로 맵에
																			// 저장
			}
		}

		int min = 987654321;
		int hei = 0;
		for (int X : hsmap.keySet()) { // 키 값을 하나씩 빼서 어떤 높이의 블럭을 하나 지정
			int sum = 0;
			int copyB = B;
			for (int C : hsmap.keySet()) {
				if (X < C) { // 문제의 1번 조건 , 블럭을 부시는 경우
					sum += (C - X) * hsmap.get(C) * 2;
					copyB += (C - X) * hsmap.get(C);
				} else if (X > C) {// 문제의 2번 조건 , 블럭을 쌓는 경우
					sum += (X - C) * hsmap.get(C);
					copyB -= (X - C) * hsmap.get(C);
				}
			}
			if (min >= sum && copyB >= 0) {
				min = sum;
				hei = Math.max(hei, X);
			}
		}
		System.out.println(min + " " + hei);
	}
}

tjdgur23 3년 전 0

풀었네요 ㅠ

높이의 최댓값과 최솟값 중간에 있는 값도 집터의 땅의 높이가 될 수 있다는 것을 간과했네요

homechan77 1년 전 0

tjdgur23님 저도 최대/최소값만 가지고 계산해서 계속 헤맸는데 덕분에 문제 해결하였습니다. 감사합니다 :)

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

문제

문제

출처

ICPC

반례를 찾습니다 ㅠ

tjdgur23 3년 전 0

tjdgur23 3년 전 0

homechan77 1년 전 0

tjdgur23님 저도 최대/최소값만 가지고 계산해서 계속 헤맸는데 덕분에 문제 해결하였습니다. 감사합니다 :)

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말