BOJ 9466 : 텀 프로젝트 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net DFS 문제이다. 크게 어렵지는 않은데, 주의할 만한 점은 vertex의 개수가 100000이므로 (edge의 개수도 당연히 100000이다) 모든 정점에 대해 BFS를 수행하면 O(VE)니까 TLE가 뜬다. 따라서 한 번 방문한 vertex에 대해서는 다시 방문하면 안 되고, cycle이 발생하는 경우에도 잘 체크를 해 줘야 한다. 어떤 방식으로든 한 번 방문한 ver..

https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net priority queue(max heap)과 greedy 문제다. 중요한 아이디어는 앞 시간부터 데드라인을 계산하면 고려할 대상이 너무 많아지니 뒷 시간부터 데드라인을 계산하는 것이다. 만약 현재가 시간 t라면, 데드라인이 t보다 큰 모든 문제 중에서 가장 점수가 큰 문제를 골라서 해결하면 된다. 이 경우 시간 t까지 보았을 때 얻을 수 있는 점수 중에서 가장 큰 점수를 얻게 되므로 시간 1이 되었을 때..

매우 간단한 greedy와 sort 문제이다. 입력받은 물이 새는 위치를 정렬하고, 정렬된 값을 앞에서부터 테이프를 가장 많이 남기는 방식으로 붙여나가면 된다. 이것의 정당성 증명은 간단하다. 특정 물이 새는 위치 leak[i]까지만 보았을 때, leak[i]가 이미 테이프로 cover되어 있다면 테이프를 붙이지 않는 것이 자원을 가장 아끼는 방법이고, 테이프가 cover되어 있지 않다면 테이프를 가장 많이 남기는 방식으로, 즉 leak[i]-0.5 지점부터 붙이는 것이 가장 자원을 아끼는 방법이다. leak[i]까지만 보았을 때는 이보다 효율적인 방법은 없고, leak[n]까지 이를 반복하면 된다. 시간복잡도는 NlogN + N = O(NlogN)이다. 1 2 3 4 5 6 7 8 9 10 11 12 ..