알고리즘/문제풀이

백트래킹(금공강 사수 / S1) - 27375

문승주 2023. 7. 2. 21:39
반응형

1. 문제

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

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

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

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

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

 

2. 입력

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

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

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

 

3. 출력

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

1

 

4. 코드

- 파이썬

import sys

input = sys.stdin.readline
n, k = map(int, input().split())

classList = [[] for _ in range(5)]
for i in range(n):
  w, s, e = map(int, input().split())
  if w == 5:
    continue
  classList[w].append((s, e))
  classList[w].sort()

# 시간별로 정렬
for i in range(4):
  classList[i].sort()

def dfs(day, edClass, score):
  global cnt
  # 학점초과시 return
  if score > k:
    return
  # 학점채울시 cnt+1하고 return
  if score == k:
    cnt += 1
    return
  for i in range(day, 5):
    for st, ed in classList[i]:
      # 다음 요일이거나 다음시간이거나
      if day == i and edClass < st or day < i:
        score += (ed - st + 1)
        dfs(i, ed, score)
        score -= (ed - st + 1)

global cnt
cnt = 0
# (요일, 끝나는 시간, 학점)
dfs(1,0,0)
print(cnt)

 

- 자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

class Main {
    static List<List<int[]>> classList;

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

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        classList = new ArrayList<List<int[]>>();
        for (int i = 0; i < 5; i++) {
            classList.add(new ArrayList<int[]>());
        }

        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());
            if (w == 5) {
                continue;
            }
            classList.get(w).add(new int[]{s, e});
        }

        for (List<int[]> list : classList) {
            Collections.sort(list, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0] - o2[0];
                }
            });
        }

        int cnt = dfs(1, 0, 0, k);
        System.out.println(cnt);
    }

    static int dfs(int day, int edClass, int score, int k) {
        int cnt = 0;
        if (score > k) {
            return 0;
        }
        if (score == k) {
            return 1;
        }
        for (int i = day; i < 5; i++) {
            for (int[] interval : classList.get(i)) {
                int st = interval[0];
                int ed = interval[1];
                if (day == i && edClass < st || day < i) {
                    int newScore = score + (ed - st + 1);
                    cnt += dfs(i, ed, newScore, k);
                }
            }
        }
        return cnt;
    }
}

 

5. 풀이설명

① 입력값으로 수업의 개수 n 과 윤헌이가 듣고 싶은 학점 k를 입력받는다.

 

② 길이가 5인(평일)동안의 classList를 생성한다.

 

③ n만큼 for문 실행하는데 요일 변수 w, 수업의 시작 교시 , 끝 교시 

 

 

 

 

 

- score에 ed-st +1의 수업시간을 뺀다.

 

⑧ dfs 함수가 끝나면 cnt를 결과값으로 출력한다.

 

6. 느낀점

백트래킹 문제는 전반적으로 dfs를 실행하는데 실행전 매개변수를 변경시키고 재귀 함수 호출 재귀함수 호출이 끝나면 매개변수인 값을 원래대로 돌리는 것을 반복하는 것 같다.

반응형