[백준] 1263 - 시간 관리

1. 문제

1263번: 시간 관리

2. 개요

N개의 할 일이 있다.

이 일들은 각각 소요시간과 데드라인이 있다.

0시부터 활동을 시작할 수 있고 두 개 이상의 일을 같은 시간에 처리할 수 없다.

모든 일을 각각의 마감시간 내에 처리하려고 할 때, 일을 가장 늦게 시작할 수 있는 때를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

가장 늦은 데드라인을 기준으로 schedule 배열 하나를 만들고 데드라인이 늦은 일부터 탐색하여 처리시간 만큼 앞으로 나가며 schedule 배열을 채워넣는다. 또한 answer도 해당 인덱스로 갱신한다.

schedule의 0번 인덱스가 채워져있는데 남은 일감이 있다면 모든 일을 처리할 수 없는 경우이므로 answer 를 -1로 갱신한다.

탐색을 끝내고 answer를 출력한다.

3-2. Python

import sys

N = int(sys.stdin.readline())

tasks = []
for i in range(N):
    tasks.append(list(map(int, sys.stdin.readline().split())))

tasks.sort(key = lambda x : -x[1])

answer = 0
schedules = [0 for i in range(tasks[0][1])]

for t in tasks:
    for i in range(t[1] - 1, -1, -1):
        if t[0] == 0:
            break

        if schedules[i] == 0:
            answer = i
            schedules[i] = 1
            t[0] -= 1
            continue

    if t[0] > 0:
        answer = -1
        break

print(answer)

3-3. C#

namespace boj_1263
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            List<int[]> tasks = new List<int[]>();

            for (int i = 0; i < N; i++)
            {
                tasks.Add(Array.ConvertAll(Console.ReadLine().Split(), int.Parse));  
            }

            tasks = tasks.OrderBy(x => -x[1]).ToList();

            int answer = 0;
            int[] schedules = new int[tasks[0][1]];

            foreach (int[] task in tasks)
            {
                for (int i = task[1] - 1; i > -1; i--)
                {
                    if (task[0] == 0)
                        break;

                    if (schedules[i] == 0)
                    {
                        answer = i;
                        schedules[i] = 1;
                        task[0]--;
                        continue;
                    }
                }

                if (task[0] > 0)
                {
                    answer = -1;
                    break;
                }
            }

            Console.WriteLine(answer);
        }
    }
}