Priority Queue

CS/PS
[BOJ] 9466, 1202, 14003, 2166
BOJ 9466 : 텀 프로젝트 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net DFS 문제이다. 크게 어렵지는 않은데, 주의할 만한 점은 vertex의 개수가 100000이므로 (edge의 개수도 당연히 100000이다) 모든 정점에 대해 BFS를 수행하면 O(VE)니까 TLE가 뜬다. 따라서 한 번 방문한 vertex에 대해서는 다시 방문하면 안 되고, cycle이 발생하는 경우에도 잘 체크를 해 줘야 한다. 어떤 방식으로든 한 번 방문한 ver..
→2021.09.01
CS/PS
[BOJ] 1781번 : 컵라면
https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net priority queue(max heap)과 greedy 문제다. 중요한 아이디어는 앞 시간부터 데드라인을 계산하면 고려할 대상이 너무 많아지니 뒷 시간부터 데드라인을 계산하는 것이다. 만약 현재가 시간 t라면, 데드라인이 t보다 큰 모든 문제 중에서 가장 점수가 큰 문제를 골라서 해결하면 된다. 이 경우 시간 t까지 보았을 때 얻을 수 있는 점수 중에서 가장 큰 점수를 얻게 되므로 시간 1이 되었을 때..
→2021.07.20

• 이전
• 1
• 다음