[BOJ/Silver 1] 백준 27375 금공강 사수(C++)

문제 링크

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번 수업의 요일, 시작 교시, 끝 교시 wi, si, ei가 공백으로 구분되어 주어진다.

출력

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

제한

•  1 ≤ n ≤ 20
•  1 ≤ k ≤ 22
•  1 ≤ wi ≤ 5
•  1 ≤ si ≤ ei ≤ 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학점을 들을 수 있다. 그 이외의 경우는 불가능하다.

알고리즘 분류

• 백트래킹

풀이

일단 금공강을 원하기 때문에 금요일 수업인, 즉 W가 5인 수업은 벡터에 저장하지 않는다.

최대 n개의 수업을 벡터에 저장한 후 완전 탐색을 통해 k학점을 완성한다.

수업을 담을 때에는 시작 교시 s부터 끝 교시 e까지를 전부 방문했다고 기록한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 11
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct LECTURE {
    int W, S, E;
};

int N, K, W, S, E;
vector<LECTURE> Lecture;
bool Visited[MAX][MAX];
int Answer;

void input() {
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        cin >> W >> S >> E;
        if (W != 5) {
            Lecture.push_back({ W,S,E });
        }
    }
}

void DFS(int Score, int Index) {
    if (Score > K) {
        return;
    }
    if (Score == K) {
        Answer++;
        return;
    }

    for (int i = Index; i < Lecture.size(); i++) {
        int NowW = Lecture[i].W;
        int NowS = Lecture[i].S;
        int NowE = Lecture[i].E;
        bool Flag = true;
        for (int j = NowS; j <= NowE; j++) {
            if (Visited[NowW][j]) {
                Flag = false;
            }
        }
        if (Flag) {
            for (int j = NowS; j <= NowE; j++) {
                Visited[NowW][j] = true;
            }
            DFS(Score + NowE - NowS + 1, i + 1);
            for (int j = NowS; j <= NowE; j++) {
                Visited[NowW][j] = false;
            }
        }
    }
}

void settings() {
    DFS(0, 0);
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}