[CodeForce Beta Round #4] B. Before an Exam

 

 

 

문제 출처 : 링크

 

Input으로 요일 수(d)와 최대 시간(sumTime)이 주어진다.

그리고 d만큼 하루에 공부할 수 있는 최소 시간과 최대 시간이 각각 한 줄씩 들어온다.

 

모든 요일에 주어진 최소 시간만큼은 공부를 해야 하고, 최대 시간과 일치하는 공부 시간을 출력해야 한다.

 

주어진 요일의 공부시간동안 최대 시간만큼 할 수 없으면 "NO"를 출력하고, 가능하면 "YES"와 함께 요일별 공부시간을 출력해야 한다.

 

예)

2 5
0 1
3 5

 

d = 2고, sumTime = 5다.

이틀동안 5시간의 공부를 해야한다.

첫째날은 0~1시간 공부를 할 수 있고, 둘째날은 3~5시간을 공부할 수 있다.

 

첫째날에 1시간 공부 & 둘째날에 4시간 공부

or

첫째날 0시간 공부 & 둘째날에 5시간 공부

 

두가지 경우로 가능하기 때문에 YES다. 시간 출력은 가능한 1 4나 0 5 모두 정답처리 된다.

 

 

문제 접근

 

일단, sumTime의 값이 최소시간의 합 이상이고 최대시간의 합 이하여야만 한다.

이 밖의 조건은 무조건 NO다.

 

이 사이에 있는 값이면 답은 무조건 존재하며, 배열 값에 최소 시간을 저장해두고 sumTime에서 부족한 시간만큼 for문을 돌면서 더 공부할 수 있는만큼 첫 날부터 채워나가면 된다.

 

package CodeForces;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BetaRound4_SolutionB {
 
    static int d, sumTime;
    static int min, max;
    static int[] minArr;
    static int[] maxArr;
    
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        d = Integer.parseInt(st.nextToken());
        sumTime = Integer.parseInt(st.nextToken());
        
        int minNum = 0;
        int maxNum = 0;
        minArr = new int[d];
        maxArr = new int[d];
        
        for (int i = 0; i < d; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            
            min = Integer.parseInt(st.nextToken());
            max = Integer.parseInt(st.nextToken());
            minArr[i] = min;
            maxArr[i] = max-min;
            minNum += min;
            maxNum += max;
        }
        
        if(sumTime < minNum || sumTime > maxNum) System.out.println("NO");
        else {
            System.out.println("YES");
            
            int n = sumTime - minNum;
            
            for (int i = 0; i < d; i++) {
                
                if(maxArr[i] <= n) {
                    minArr[i] += maxArr[i];
                    n -= maxArr[i];
                    if(n == 0) break;
                }
                else { // maxArr[i] > n
                    minArr[i] += n;
                    break;
                }
            }
            
            for (int i = 0; i < minArr.length; i++) {
                System.out.print(minArr[i] + " ");
            }
        }
    }
 
}