[백준] 27375 - 금공강 사수 (python)

 

문제

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

고려대학교에서 수강할 수 있는 n개의 수업의 요일과 시작 교시, 끝 교시가 주어진다. 요일 w는 월요일부터 금요일까지 각각 1부터 5까지의 정수로 주어지며, 수업의 시작 교시 s, 끝 교시 e가 1부터 10까지의 정수로 주어진다. 수업의 학점은 e-s+1이다.

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

이때, 같은 요일, 같은 교시에 열리는 두 수업은 동시에 수강할 수 없다. 예를 들어, 화요일 5교시부터 7교시까지 열리는 수업과 화요일 7교시부터 9교시까지 열리는 수업은 동시에 수강할 수 없다.

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

입력

첫 줄에 수강 가능한 수업의 개수 n과 윤헌이가 듣고 싶은 학점 k가 공백으로 구분되어 주어진다.

다음 n번째 줄에는 i번 수업의 요일, 시작 교시, 끝 교시 w, s, e가 공백으로 구분되어 주어진다.

출력

 

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

 

 

 

풀이

 

백트래킹 문제이다.

 

DFS를 이용한 평범한 백트래킹 문제이지만, 수업의 시간이 겹칠 경우를 구분해주어야 한다.

 

나는 flag 리스트를 따로 만들고, flag 리스트에 있는 수업들을 중간에 겹치는지 여부를 한번 더 검사하였다.

 

 

 

코드

 

import sys

input = sys.stdin.readline

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

for _ in range(n):
    w, s, e = map(int, input().split())
    score = e - s + 1
    li.append((w, s, e, score))
cnt = 0

flag=[False]*n

def cal_score(score, c, flag):
    global cnt
    if score == k:
        cnt += 1
        return
    if score > k:
        return
    for i in range(c + 1, n):
        if li[i][0] != 5 and not flag[i]:
            take=True
            for j in range(i):
                if flag[j]:
                    if li[i][0] == li[j][0]:
                        if not (li[i][1] > li[j][2] or li[i][2] < li[j][1]):
                            take=False
                            break
            if take:
                flag[i]=True
                cal_score(score + li[i][3], i, flag)
                flag[i]=False


for i in range(n):
    if li[i][0] != 5:
        flag[i]=True
        cal_score(li[i][3], i, flag)
        flag[i]=False

print(cnt)