8/23 Problem Solving

2623 음악프로그램 (G3)

 

각 PD들의 가수 출연 순서에 따라 단방향 그래프를 만든다. 그 다음에 Topological Sort를 해줘서 전체 출연 순서를 정한다. Directed Acyclic Graph를 이루면 전체 가수의 수만큼 정확히 출력이 될것이고 아니면 순서 정하는 것이 불가능하므로 0을 출력한다.

 

http://boj.kr/09f1e0b6e82c457e89e3a05fb6143178

 

 

4386 별자리 만들기 (G3)

 

각 별들의 좌표를 정점으로 생각하고 좌표들 간의 거리를 간선으로 생각하면 그래프를 구성할 수 있다. 그리고 Minimum Spanning Tree를 구성하면 별자리를 만드는 최소 비용을 구할 수 있다.

 

http://boj.kr/a587be0a5a53456583384ae27fbc07e7

 

 

2812 크게 만들기 (G3)

 

지우는 횟수를 K번해서 숫자를 최대한 크게 만들어야 한다. 스택을 하나 두고 높은 자리 숫자부터 하나씩 보면서 현재 보는 숫자보다 스택에 있는 숫자가 더 작으면 최대 K번 pop해준다. 이후 지우는 횟수가 남아 있다면 뒤에서부터 남은 횟수만큼 숫자를 제거해준다.

 

http://boj.kr/50eb8154438b47f18e79ee8234f515af

 

 

2342 Dance Dance Revolution (G3)

 

d[i][l][r] = i번째 지시까지 수행하고 나서 왼발이 l, 오른발이 r에 위치할 때 드는 최소 힘

 

현재 상태에서 다음 지시를 수행할 때 왼발이 움직이는 경우와 오른발이 움직이는 경우 중 최소 비용을 선택한다.

 

http://boj.kr/74e5d6ae20b24383befcf8a8cfeb1fac

 

 

13904 과제 (G3)

 

과제들을 점수가 높은 순으로 정렬한다. 그리디하게 점수가 높은 과제부터 최대한 마감일에 가깝게 늦게 배치할 수록 최대한 많은 점수를 얻을 수 있다.

 

http://boj.kr/8afe524d1f2441aca12572905eb3d7e3