8/28 Problem Solving

14172 Moocast (G5)

 

모든 소들의 쌍에 대해서 a->b로 가는 거리가 power 안에 들어오면 간선으로 이어준다. 거리를 계산할때 제곱끼리 비교해서 실수 연산을 최대한 피해준다. 그리고 모든 점에 대해서 BFS로 도달할 수 있는 소들의 최댓값을 구해주면 된다.

 

http://boj.kr/a841ac2eadbe418ba6030ddad02d28e9

 

 

14464 소가 길을 건너간 이유 4 (G1)

 

소들을 Bj를 기준으로, Bj가 같다면 Aj를 기준으로 정렬한다. 닭은 Ti를 기준으로 오름차순 정렬한다. 그리고 소들을 한 마리씩 보면서 그리디하게 Ti가 가장 작은 닭에게 매칭시켜주면 된다.

 

http://boj.kr/e5b7f5e2de2f400e874a91d1cd9820d0

 

 

2109 순회강연 (G3)

 

강연들을 기한에 따라 오름차순으로 정렬한다. 이로 인해 먼저 도착한 날짜부터 처리할 수 있게 된다. 우선순위 큐를 이용하여 현재 선택된 강연료들을 저장하고 기한이 지나치면 최소 강연료를 가진 강연을 제거하는 방식으로 최대 수익을 구할 수 있다.

 

http://boj.kr/a5eda6722dab487190999df250fc889f

 

 

7432 디스크 트리 (G3)

 

디렉토리 구조를 트라이로 표현하고 루트에서 시작해서 재귀적으로 출력해준다.

 

http://boj.kr/8340afeb8efb46a6a13ea173de515182

 

 

10198 Crossing River (G3)

 

점프할 수 있는 범위를 전체 탐색 구간으로 두고 parametric search를 한다. possible 함수에서 현재 정해진 범위로 강을 건널 수 있는지 확인한다. 건널 수 있으면 다음 구간을 아래로 내리고 건널 수 없으면 다음 구간을 위로 올린다.

 

http://boj.kr/1c629ce24f2849d498dafadb0c8f7e90