문제 해설
Difficulty : *1200 (Constructive Alg. / Greedy)
피터는 과연 시험 날짜 전까지 필요한 공부를 완벽하게 할 수 있을까요? 주어진 일자 내에 주어진 시간만큼의 할당량을 정확하게 해소할 수 있는지 판단하고 그 할당량을 일자별로 출력하는 문제입니다.
첫 줄에 남은 일자와 필요한 공부량(시간)이 입력됩니다. 그 다음 줄부터 각 날짜당 할 수 있는 공부량의 최소, 최대치가 입력됩니다.
각 날짜에 할 수 있는 공부량은 해당 날짜에 지정된 최대, 최소치 범위를 벗어날 수 없습니다.
모든 날짜에 최대치로 공부해도 필요한 공부량을 달성할 수 없거나 모든 날짜에 최소치를 공부해도 필요한 공부량을 넘으면 ‘NO’를 출력합니다. 기간내에 정확하게 달성할 수 있다면 ‘YES’ 출력 후 줄바꿈하여 날짜별 공부한 시간을 공백을 두고 출력합니다.
가능한 경우의 수가 여러개라면, 아무 경우나 출력합니다.
풀이
날짜별 공부량 최대, 최소치를 배열로 입력받고 모든 날짜의 최대치(max)와 목표치(limitTime)를 비교하여 달성 가능 여부부터 판단합니다.
불가능할 경우 : ‘NO’ 출력으로 종료.
가능할 경우 : ‘Yes’ 출력 후 다음 단계 진행.
max가 목표치와 같다면 각 날짜별로 최대치를 그대로 출력 배열에 입력 후 출력합니다. max가 더 크다면 맨 뒤 날짜부터 공부량을 1씩 줄여 목표치와 동일할 때까지 맞춘 후 출력합니다. 이 때, 각 날짜별 최소 공부량을 벗어나지 않도록 합니다. 만약 모든 날짜에 최소치로 공부해도 목표치를 넘는다면 달성 불가능으로 판단하여 ‘NO’를 출력합니다.
코드
C
#include <stdio.h>
int main() {
int day, limitTime, i, max = 0;
scanf("%d %d", &day, &limitTime);
int flag = day - 1;
int minmax[day][2];
//최소최대 시간 입력
for(i = 0; i < day; i++){
scanf("%d %d", &minmax[i][0], &minmax[i][1]);
max += minmax[i][1];
}
//전체 최대치가 필요량과 같다면 그대로 출력
if(max == limitTime){
printf("YES\n");
for(i = 0; i < day; i++){
printf("%d ", minmax[i][1]);
}
}
else if(max > limitTime){
//전체 최대치가 필요량보다 많다면 일별 최소 시간을 유의하며 1씩 감소
while(max != limitTime){
if(minmax[flag][1] > minmax[flag][0]){
minmax[flag][1] -= 1;
max--;
}
else{
//전체 최소치가 필요량보다 크다면 달성 불가능
if(flag == 0){
printf("NO");
return 0;
}
flag--;
}
}
printf("YES\n");
for(i = 0; i < day; i++){
printf("%d ", minmax[i][1]);
}
}
//전체 최대치가 필요량보다 적다면 달성 불가능
else{
printf("NO");
}
return 0;
}
C++
#include <iostream>
int main() {
int day = 1, limitTime = 0, max = 0;
std::cin >> day >> limitTime;
int flag = day - 1;
int** minmax = (int**)malloc(sizeof(int*) * day);
for(int i = 0; i < day; i++){
minmax[i] = (int*)malloc(sizeof(int) * 2);
}
//최소최대 시간 입력
for(int i = 0; i < day; i++){
std::cin >> minmax[i][0] >> minmax[i][1];
max += minmax[i][1];
}
//전체 최대치가 필요량과 같다면 그대로 출력
if(max == limitTime){
std::cout << "YES" << std::endl;
for(int i = 0; i < day; i++){
std::cout << minmax[i][1] << " ";
}
}
else if(max > limitTime){
//전체 최대치가 필요량보다 많다면 일별 최소 시간을 유의하며 1씩 감소
while(max != limitTime){
if(minmax[flag][1] > minmax[flag][0]){
minmax[flag][1] -= 1;
max--;
}
else{
//전체 최소치가 필요량보다 크다면 달성 불가능
if(flag == 0){
std::cout << "NO" << std::endl;
return 0;
}
flag--;
}
}
std::cout << "YES" << std::endl;
for(int i = 0; i < day; i++){
std::cout << minmax[i][1] << " ";
}
}
//전체 최대치가 필요량보다 적다면 달성 불가능
else{
std::cout << "NO" << std::endl;
}
return 0;
}
Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int day, limitTime, max = 0;
Scanner sc = new Scanner(System.in);
day = sc.nextInt();
limitTime = sc.nextInt();
int flag = day - 1;
int minmax[][] = new int[day][2];
//최소최대 시간 입력
for(int i = 0; i < day; i++){
minmax[i][0] = sc.nextInt();
minmax[i][1] = sc.nextInt();
max += minmax[i][1];
}
//전체 최대치가 필요량과 같다면 그대로 출력
if(max == limitTime){
System.out.println("YES");
for(int i = 0; i < day; i++){
System.out.print(minmax[i][1] + " ");
}
}
else if(max > limitTime){
//전체 최대치가 필요량보다 많다면 일별 최소 시간을 유의하며 1씩 감소
while(max != limitTime){
if(minmax[flag][1] > minmax[flag][0]){
minmax[flag][1] -= 1;
max--;
}
else{
//전체 최소치가 필요량보다 크다면 달성 불가능
if(flag == 0){
System.out.println("NO");
return;
}
flag--;
}
}
System.out.println("YES");
for(int i = 0; i < day; i++){
System.out.print(minmax[i][1] + " ");
}
}
//전체 최대치가 필요량보다 적다면 달성 불가능
else{
System.out.println("NO");
}
return;
}
}
Python
day, limitTime = map(int, input().split())
maxnum = 0
flag = day - 1;
minmax = [[0 for col in range(2)] for row in range(day)]
#최소최대 시간 입력
for i in range(0, day):
minmax[i][0], minmax[i][1] = map(int, input().split())
maxnum += minmax[i][1]
#전체 최대치가 필요량과 같다면 그대로 출력
if maxnum == limitTime:
print("YES")
for i in range(0, day):
print((int)(minmax[i][1]), end=" ", flush = True)
elif maxnum > limitTime:
#전체 최대치가 필요량보다 많다면 일별 최소 시간을 유의하며 1씩 감소
while maxnum != limitTime:
if minmax[flag][1] > minmax[flag][0]:
minmax[flag][1] -= 1
maxnum -=1
else:
if flag == 0: #전체 최소치가 필요량보다 크다면 달성 불가능
print("NO")
quit()
flag -=1
print("YES")
for i in range(0, day):
print((int)(minmax[i][1]), end=" ", flush = True)
else: #전체 최대치가 필요량보다 적다면 달성 불가능
print("NO")
quit()