글 읽기 - 2512 예산 문제 질문입니다

darkziny22 9년 전 0

테스트 케이스를 여러개 돌려봐도 어느 부분에서 틀렸는지 잘 모르겠습니다

m,n의 입력 범위를 if문으로 감싸도 틀렸다고 하는것을 보니

틀린 부분이 있긴 한 것 같은데...

대체 어디가 문제인거죠?

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

public class Main {

	private static int n = 0;
	private static int m = 0;
	private static int input = 0;
	private static int arr[];

	private static int sum = 0;
	private static int avg = 0;
	private static int count = 0;

	public static void main(String[] args){
		run();
	}

	public static void run(){
		Scanner sc = new Scanner(System.in);

		int flag = 0;

		n = sc.nextInt();
		count = n; 

		if(n>=3 && n<10000){
			arr = new int[n];

			for(int i=0; i<n; i++){
				input = sc.nextInt();
				arr[i] = input;
				sum += input;				// 요청의 총액
			}
			m = sc.nextInt();				// 예산의 한도
			
			Arrays.sort(arr);				// 오름차순 정렬

			process();
			
		}
	}
	public static void process(){
		if(m>=sum){					// 예산 범위 내에 있을 경우, 가장 큰 값을 출력
			System.out.println(arr[n-1]);
		}else{						// 예산을 초과하는 경우
			sum = m;
			avg = m/n;

			for(int j=0; j<n; j++){
				// 총액의 평균값보다 낮은 값은 총액에서 빼줌
				if(arr[j]<=avg){		sum-=arr[j];	count--;}
			}
			System.out.println(sum/count);	// 총액에서 초과하는 예산에 대한 평균 출력
		}

	}
}

zzapCoder 9년 전 1

주어진 예산을 n으로 나누고, 이 값보다 작은 것들에서 남는 부분을 다시 걷어 나누어 준 셈이네요.

그런데 다시 걷어 나누어 줬는데 또 남으면 처리를 또 해줘야 합니다.

50 50 50 50 100 100 120 120 200 240

1000

을 넣으면 질문자님의 코드는 150을 출력합니다. 다시 한번 생각해 보세요.

darkziny22 9년 전 0

@zzapCoder 님께서 지적해 주신대로

한번의 수행으로 끝나지 않을 수 있는데, 그 경우를 생각하지 못했네요..

그래서 그런 경우가 발생하지 않을 때까지 반복하도록 코드를 수정했는데

이전의 테스트 케이스와 올려주신 테스트 케이스를 만족해서 통과될 줄 알았는데

또 실패네요... 아... 이번엔 또 뭐가 문제죠

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

public class Main {

	private static int n = 0;
	private static int m = 0;
	private static int input = 0;
	private static int arr[];

	private static int sum = 0;
	private static int avg = 0;
	private static int count = 0;

	public static void main(String[] args){
		run();
	}

	public static void run(){
		Scanner sc = new Scanner(System.in);

		int flag = 0;

		n = sc.nextInt();
		count = n; 

		if(n>=3 && n<10000){
			arr = new int[n];

			for(int i=0; i<n; i++){
				input = sc.nextInt();
				arr[i] = input;
				sum += input;				// 요청의 총액
			}
			m = sc.nextInt();				// 예산의 한도
			
			Arrays.sort(arr);				// 오름차순 정렬

			process(0,m);
		}
	}
	
	public static void process(int start, int budget){
		if(m>=sum)	System.out.println(arr[n-1]);	// 한도 이내의 경우
		else{								// 한도 초과인 경우
			int temp = budget;
			int idx = 0;
			int average = temp/count;
			
			for(int i=start; i<n; i++){
				if(arr[i]<=average){
					m -=arr[i];	count--;
				}else{					// 통과되지 못하는 예산의 인덱스를 저장
					idx= i;	break;
				}
			}
			
			// 통과되지 못한 나머지 예산에 대해서 처리
			
			// 나머지 예산으로 통과될 수 없는 경우, 남은 예산을 남은 도시수로 나눠서 출력
			if(idx==start)	System.out.println(m/count);
			else process(idx, m);	// 가능한 경우는 한번 더 수행
		}
	}
}

darkziny22 9년 전 1

허허...

이전에 풀었던 문제들도 그렇고 이 문제도 그렇고

문제에서 주어진 N, M의 범위를 만족시키는 값만 통과하도록 한 if문을 없애니 통과되네요...;;

뭔가 허무하군요

어쨌거나 도움주신 @zzapCoder 님 감사합니다:)

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

문제

문제

출처

ICPC

2512 예산 문제 질문입니다

darkziny22 9년 전 0

zzapCoder 9년 전 1

darkziny22 9년 전 0

darkziny22 9년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말