글 읽기 - 반례를 알고싶습니당!

mihyunhaha 2년 전 0

집 위치 별로 안테나를 설치했을 때, 거리를 각각 구해서 최솟값을 가지는 집위치를 출력하도록 코드를 작성하였는데 자꾸 틀려서 질문드립니다.

import java.util.ArrayList;
import java.util.Arrays;	
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt(); // 집의 수
		int[] arr = new int[N]; // 집 위치
		ArrayList<Integer> list = new ArrayList<Integer>(); // 중복을 제거한 집 위치
		
		
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();			
		}
		
		Arrays.sort(arr);
		
		list.add(arr[0]);
		for (int i = 1; i < N; i++) {
			if(arr[i] != arr[i-1]) {
				list.add(arr[i]); 
			}
		}
	
		// arr 배열에 집 위치 전체 넣기, list에 중복 제거 집 위치 넣어서 list의 각 원소별 '거리 최솟값' 구하고 그때의 list '원소값' 출력하기
		int res = Integer.MAX_VALUE; // 거리 최솟값
		int ans = -1; // 원소값
		
		for (int i = 0; i <list.size() ; i++) {
			int dist = 0; 
			for (int j = 0; j < arr.length; j++) {
				dist += Math.abs(list.get(i)-arr[j]);
			}
			
			if (res > dist) {
				res = dist; // res 갱신
				ans = list.get(i);
			}

		}
		System.out.println(ans);
	}
    
}

djm03178 2년 전 1

거리의 합이 int의 범위를 넘어갈 수 있습니다.

zooyeonii 2년 전 0

반례도 중요하지만, 중앙값의 성질에 대해 생각해보시면 더 간단하게 푸실 수 있습니다.

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

문제

문제

출처

ICPC

반례를 알고싶습니당!

mihyunhaha 2년 전 0

djm03178 2년 전 1

zooyeonii 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말