[백준] 27375번 : 금공강 사수

https://www.acmicpc.net/problem/27375

27375번: 금공강 사수

문제

윤헌이는 수강신청 시즌이 되어 시간표를 짜고 있다. 지난 학기 금요일에 수업을 들어 친구들에게 온갖 놀림을 받은 윤헌이는 이번 학기에는 꼭 금요일 공강을 지켜내기로 결심했다!!

고려대학교에서 수강할 수 있는

$n$개의 수업의 요일과 시작 교시, 끝 교시가 주어진다. 요일 $w$는 월요일부터 금요일까지 각각 1부터 5까지의 정수로 주어지며, 수업의 시작 교시 $s$, 끝 교시 $e$가 $1$부터 $10$까지의 정수로 주어진다. 수업의 학점은

$e-s+1$이다.

이번 학기에

$k$ 학점을 듣고 싶은 윤헌이는 금요일에 공강이 있는 시간표의 가짓수가 궁금하다.

이때, 같은 요일, 같은 교시에 열리는 두 수업은 동시에 수강할 수 없다. 예를 들어, 화요일

$5$교시부터 $7$교시까지 열리는 수업과 화요일 $7$교시부터

$9$교시까지 열리는 수업은 동시에 수강할 수 없다.

윤헌이를 위해 정확히

$k$ 학점을 들으면서 금요일에 수업이 하나도 없는 시간표의 가짓수를 구해 보자!

입력

첫 줄에 수강 가능한 수업의 개수

$n$과 윤헌이가 듣고 싶은 학점

$k$가 공백으로 구분되어 주어진다.

다음

$i$번째 줄에는 $i$번 수업의 요일, 시작 교시, 끝 교시

$w_i, s_i, e_i$가 공백으로 구분되어 주어진다.

출력

정확히

$k$ 학점을 들으면서 금요일에 수업이 하나도 없는 시간표의 가짓수를 출력한다.

 

코드

n, k = map(int, input().split())
classes = []

for i in range(n):
    days, start, end = map(int, input().split())
    if days != 5:
        classes.append([days, start, end])

result = 0

c = [[0]*11 for _ in range(6)]

def backtracking(idx, score):
    global result
    if idx == len(classes) or score >= k:
        if score == k:
            result += 1
            return

    for i in range(idx, len(classes)):
        flag = True
        for j in range(classes[i][1], classes[i][2]+1):
            if c[classes[i][0]][j] == 1:
                flag = False
        if flag == True:
            for j in range(classes[i][1], classes[i][2] + 1):
                c[classes[i][0]][j] = 1
            backtracking(i+1, score+classes[i][2]-classes[i][1]+1)
            for j in range(classes[i][1], classes[i][2] + 1):
                c[classes[i][0]][j] = 0


backtracking(0, 0)
print(result)

1. 먼저 금요일 수업은 듣지 않아야 하므로 요일이 5인 경우는 classes 리스트에 저장하지 않는다.

 

2. 내가 해당 수업을 듣고 있다고 가정하고 다음 수업을 고민해 볼 수 있도록 c라는 리스트를 생성한다.

(이때, 교시는 1~10교시가 있고 요일은 월~금까지 있으므로 c의 크기는 [[0]*11 for _ in range(6)] 으로 했는데 금요일은 고려하지 않았으므로 요일은 월~목까지만 있다고 가정하고 c의 크기를 [[0]*11 for _ in range(5)]로 설정해도 좋다.)

 

3. 각 수업에 대하여 내가 이전에 듣기를 가정한 수업과 현재 고려해보고 있는 수업의 시간이 겹치는지 아닌지를 판별한다.

 

4. 만약 겹치지 않는다면 해당 수업을 이수했을 때의 학점을 매개변수 score에 더한다.

 

5. 만약 전체 강의를 고려해봤거나 이수한 학점이 k 이상일 때, 현재 내가 고려한 수업들의 학점이 정확이 k라면 result를 1더해준다.