티스토리 뷰

문제 링크


E. 닉네임에 갓 붙이기


$N$개의 닉네임이 음절 단위로 쪼개져 주어진다. 첫 음절을 제외하고, 맨 앞에 "god"을 붙여 출력하는 문제다.


줄 별로 입력받고 입력 받은 문자열을 공백으로 나누어 문자열 배열로 만들어주면 된다. C, C++에서 이는 strtok 함수를 통해 간단히 해결할 수 있다.


코드 보기


F. 행복 유치원


오름차순으로 정렬된 길이 $N$인 배열이 주어진다. 이 배열을 $K$개의 파티션으로 나누는데 각 파티션에 해당하는 비용은 최대값-최소값이다. 이 때 $K$개의 파티션으로 나누었을 때 최소 비용을 구하는 문제다.


배열 $[1, 3, 4, 8, 10]$을 $[1]$, $[3, 4]$, $[8, 10]$ 세 개의 파티션으로 나누었을 때 비용은 (10 - 1) - (3 - 1) - (8 - 4) = 3이 된다. 즉, 배열이 정렬되어있으므로 인접한 두 값의 차이를 내림차순으로 정렬한 뒤 상위 $K-1$개의 값을 (전체 최대값 - 전체 최소값)에서 빼주면 답이 된다.


코드 보기


L. 떨어진 수정


강도가 $P$이하의 양의 실수로 표현되는 마나 수정 $N$개가 있다. 망치를 휘둘러 $P$이하의 강도로 마나 수정을 내리치는데, 마나 수정의 강도보다 $W$이상 강한 힘으로 내리치면 수정이 폭발하고 그보다 적은 마나 수정의 강도 이상의 힘으로 내리치면 파괴된다. 이 중 $K$번째로 강도가 쎈 마나 수정을 폭발이 아닌 파괴를 시키기 위해 최악의 경우 필요한 내리치는 회수의 최소값을 구하는 문제다.


풀이에 비해 문제 설명이 매우 복잡하다(...) 결론부터 말하면 답은 $\lceil \frac{P}{W} \rceil$ 이다. 내리치는 강도를 $W, 2W, \dots, P$로 하는 것이 최악의 경우 회수를 최소화하는 최적의 방법이다.


코드 보기


J. 내일로 여행


$N$개의 도시가 있고, $K$개의 교통 수단이 있다. 도시들을 주어진 순서대로 여행하는데, 내일로 티켓을 사면 특정 교통 수단의 비용이 감소한다. 이 때, 내일로 티켓을 사는 것이 이득인지 판단하는 문제다.


$N \leq 100$이므로 Floyd-Warshall 알고리즘을 이용해 모든 두 도시 쌍 사이를 이동하는 최단 거리를 구하는 것이 편하다. 이 때, 내일로 티켓을 사는 경우와 사지 않는 경우에 대한 인접행렬을 따로 만들어 계산하면 된다. 내일로 티켓을 살 경우 "S-Train"과 "V-Train"은 비용이 절감되므로 전체 비용 스케일을 두 배로 늘려 실수 연산을 피할 수 있다. (시간 테스트 용도로 이 문제 코드는 Java로 작성되었음)


코드 보기


B. 최대 클리크 구하기


$N$개의 정점이 있는 구간 그래프가 주어졌을 때, 최대 클리크를 구하는 문제다.


구간 그래프에서 클리크는 구간들을 아래 그림처럼 나타내었을 때, 구간들을 관통하는 수직선 하나로 볼 수 있다.



때문에 최대 클리크는 가장 많은 구간을 관통하는 수직선을 찾고 그 수직선이 관통하는 구간들을 찾는 것으로 구할 수 있다.


코드 보기


H. 범죄 파티


이분탐색으로 파티의 비용을 정하고, 정한 파티 비용으로 모든 용의자가 적어도 한 명의 변호인을 둘 수 있는지 확인하는 결정 문제를 해결한다. 결정 문제는 2-SAT 혹은 이분매칭으로 해결할 수 있다. $N \leq 200,000$으로 굉장히 커서 이분매칭으로 안될 것 같아보이지만, 이 문제에서 이분그래프 간선의 수가 최대 $2N$이므로 Hopcroft-Karp 알고리즘으로 $O(N^{1.5})$으로 해결할 수 있다.


코드 보기


저작자 표시
신고
댓글
댓글쓰기 폼