[Go] 백준 1931번 회의실 배정 (그리디)

문제

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

입력

첫째 줄에 회의의 수 N (1 <= N <= 100000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2^31-1 보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

---

문제 풀이

문제 해석 및 계획

DFS를 통하여 앞 회의가 끝나는 시간 이후의 회의들을 확인하여 깊이 중 제일 깊은 깊이를 출력하도록 생각하였습니다.

오답 노트

가장 깊은 깊이를 return 하도록 하였으나 시간 초과에 걸리게 되었습니다.

 

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main(){
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)

	defer writer.Flush()

	var N int
	fmt.Fscan(reader, &N)
	conferenceList := make([][]int, N)
	for i:=0 ; i<N ; i++ {
		var start, end int
		fmt.Fscan(reader, &start, &end)
		conferenceList[i] = []int{start, end}
	}
	max := 0
	for i:=0 ; i<N ; i++ {
		result := DFS(conferenceList, i, 1)
		if max < result {
			max = result
		}
	}
	fmt.Fprintln(writer, max)
}

func DFS(conferenceList [][]int, startNum int, cnt int) int {
	max := cnt
	for i:=0 ; i<len(conferenceList) ; i++ {
		if conferenceList[startNum][1] <= conferenceList[i][0] && startNum != i {
			result := DFS(conferenceList, i, cnt+1)
			if max < result {
				max = result
			}
		}
	}
	return max
}

정답

DFS방식으로 풀이하여도 답은 나오지만 시간을 줄이기 위해서 모든 경우를 확인하는 것이 아니라고 생각하였습니다.

고민을 한 결과 정해진 통 안에 가장 많은 공을 넣기 위해선 크기가 작은 공을 넣어야 한다고 생각되어 빨리 끝나는 회의들을 순서대로 확인하면 되겠다고 생각하였습니다.

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

type Meeting struct {
	start, end int
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)

	defer writer.Flush()
	var N int
	fmt.Fscan(reader, &N)

	meetings := make([]Meeting, N)
	for i:=0; i<N; i++ {
		fmt.Fscan(reader, &meetings[i].start, &meetings[i].end)
	}

	sort.Slice(meetings, func(i, j int) bool {
		if meetings[i].end == meetings[j].end {
			return meetings[i].start < meetings[j].start
		}
		return meetings[i].end < meetings[j].end
	})

	count := 0
	endTime := 0

	for i:=0; i<N; i++ {
		if meetings[i].start >= endTime {
			endTime = meetings[i].end
			count++
		}
	}

	fmt.Fprint(writer, count)
}

---

느낀 점

DFS도 알고리즘 중 하나로 특정 방법을 찾아내는데 효율적인 알고리즘입니다. 하지만 상황에 따라 더 효율적인 알고리즘이 존재합니다. 꾸준한 노력으로 많은 문제를 풀어보며 상황에 따라 어떠한 알고리즘이 유용할지 익혀가도록 하겠습니다.