BOJ 27375 금공강 사수

https://www.acmicpc.net/problem/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$ 학점을 들으면서 금요일에 수업이 하나도 없는 시간표의 가짓수를 출력한다.

---

제한

• $1 \le n \le 20$ 
• $1 \le k \le 22$ 
• $1 \le w_i \le 5$ 
• $1 \le s_i \le e_i \le 10$ 

---

예제 입력 1

10 15
3 4 4
3 4 9
3 6 8
1 10 10
3 2 5
2 6 10
5 5 5
2 5 7
3 6 10
3 1 6

예제 출력 1

1

4번 수업, 5번 수업, 6번 수업, 9번 수업을 들으면 1+4+5+5=15학점을 들을 수 있다. 그 이외의 경우는 불가능하다.

---

코드

요즘 은근히 정리할 내용이 많아서 간단한 문제만 풀고 있다…
이번 문제도 간단한 브루트포스 문제다.
코드도 딱히 주목해볼만한 부분 없이 무난한 것 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static class Lecture {
        int w;
        int s;
        int e;
        int credits;

        public Lecture(int w, int s, int e, int credits) {
            this.w = w;
            this.s = s;
            this.e = e;
            this.credits = credits;
        }
    }

    static int n;
    static int k;
    static int count = 0;
    static List<Lecture> lectures = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int credits = e - s + 1;

            // 수업의 학점이 k보다 크지 않고, 금요일에 진행되는 것이 아니면 추가
            if(w != 5 && credits <= k) {
                lectures.add(new Lecture(w, s, e, credits));
            }
        }

        // 요일을 기준으로 오름차순, 요일이 같으면 끝 교시를 기준으로 오름차순 정렬
        lectures.sort((l1, l2) -> {
            if (l1.w == l2.w) {
                return l1.e - l2.e;
            }

            return l1.w - l2.w;
        });

        for (int i = 0; i < lectures.size(); i++) {
            Lecture check = lectures.get(i);
            countCases(i, check.w, check.e, check.credits);
        }

        System.out.println(count);
    }

    static void countCases(int lecture, int lastW, int lastEnd, int credits) {
        if(credits == k) {
            count++;
            return;
        }

        for (int i = lecture + 1; i < lectures.size(); i++) {
            Lecture check = lectures.get(i);
            int creditsSum = credits + check.credits;

            // 현재 검사 중인 수업을 수강할 수 없거나, 수강했을 때의 총 학점이 k보다 크면 현재 수업 생략
            if(creditsSum > k || check.w == lastW && check.s <= lastEnd) {
                continue;
            }

            countCases(i, check.w, check.e, creditsSum);
        }
    }
}