티스토리 뷰

온라인 아카이브 링크


A. Number Assignment


문제에서 주어진 수들을 정렬한 다음 Dynamic Programming를 이용해 해결한다.

D[i][j] = 1~i번 수가 있고, 이를 j개의 그룹으로 나눴을 때 가능한 최소 비용 합

점화시은 아래와 같다.

D[i][j] = min(D[k][j-1] + A[i] - A[k+1]) (for j-1 ≤ k < i)

총 시간복잡도는 $O(N^2M)$이다.


코드 보기


B. Network Packet Ordering


가장 쉬운 방법으로는 $O(NM)$ Dynamic Programming을 생각할 수 있다. 하지만 이 방법은 제한 시간을 초과한다.

입력으로 두 종류 패킷이 들어온 시간이 들어오는데, 유의해야할 것은 패킷들이 들어오는 시간은 한 종류 안에서 서로 다르다. 그리고 문제 조건에서 $D \leq 100$으로 굉장히 작은 것을 알 수 있다. 따라서 기존 DP에서 $NM$개의 상태가 모두 필요하지 않음을 알 수 있다. 이를 이용해 상태의 개수를 줄이면 $O(D(N+M))$이 됨을 알 수 있다. 이 상태만을 이용하여 DP를 하면 된다.


코드 보기


C. The Busiest City


어떤 도시 $i$에서 바쁜 정도를 계산하기 위해서 도시 $i$를 루트로 한 rooted tree를 고려하면 된다. 그 때 $i$의 두 자식 노드들의 서브트리의 크기들의 곱의 합이 바쁜 정도가 된다. 이러기 위해서 자식 노드의 개수가 $C$개라 할 때, $O(C^2)$의 연산이 필요해보이지만 조금만 더 생각하면 이 계산을 $O(C)$만에 할 수 있다. 따라서, 전체 시간복잡도는 $O(N)$이 된다.


코드 보기


D. Power Plant


그냥 Minimum Cost Spanning Tree를 구하는 Kruskal 알고리즘을 생각할 수 있다. 하지만 문제 조건에서 발전소가 같은 Spanning Tree 안에 있으면 안된다는 조건이 있다. 이 조건과 상관 없이 Kruskal 알고리즘을 하여도 상관 없을을 직관적으로 알 수 있다. 따라서 Kruskal 알고리즘의 union-find 도중 union 하려는 두 집단이 각각 발전소를 포함하고 있으면 union 연산을 생략한다.


코드 보기


F. Pasti Pas!


가장 긴 Palindrom을 만들기 위해서 어떤 문자열 $S$를 $\alpha\beta\alpha$로 나타낼 수 있을 때, 가능한 가장 짧은 길이의 $\alpha$를 찾고 $\beta$에 대해서 작업을 재귀적으로 이어나가면 된다. 가장 짧은 길이의 $\alpha$가 항상 좋다라는 증명은 생략한다.

이를 수행하기 위한 두 가지 방법이 있다. 하나는 Suffix Array와 LCP, RMQ(Range Minimum Query)를 이용한 $O(N \lg N)$ 방법이고, 하나는 해싱을 이용한 $O(N)$ 방법이다. 두 방법은 두 문자열이 같은지 비교를 빠르게 하기 위해 사용된다. 전자는 확실한 정답률을 보이지만 난이도가 높다는 단점이 있으며, 후자는 확실하게 답을 알려주는 보장은 없지만 코딩이 매우 간단하단 장점이 있다. 코드는 두 가지 방법 모두 소개하겠다. 해싱의 정확도를 높이기 위해 하나의 해시 함수보다 두 개의 해시 함수를 구현하여 두 값을 비교한다.


코드 보기 (방법 1)


코드 보기 (방법 2)


G. Emergency Handling


가능한 $r$의 종류가 101가지 밖에 되지 않는다. 각 $r$ 값 마다 최대 힙(heap) 자료구조로 $t = 0$ 일 때 값을 저장해둔다. 그리고 A 종류 쿼리가 들어올 때 마다 101가지 $r$ 값에 대해서 $t = 0$ 일 때 값이 제일 큰 것을 가져와 주어진 $t$ 일 때 최대 값을 가져온다.


코드 보기


H. Horrible Quiz


Dynamic Programming을 이용해 해결 가능하다.

D[i][j] = 1번부터 i번 문제까지 풀었고, 정답지를 볼 수 있는 기회가 j번 남았을 때 최소 기대값

E[i][j] = 1번부터 i번 문제까지 풀었고, 정답지를 볼 수 있는 기회가 j번 남았을 때 최대 기대값

으로 정의한다.

점화식은 간단하게 생각할 수 있다. 위와 같이 최소, 최대 두 가지 경우에 대해서 다이나믹 배열을 정의한 이유는 문제에서 요구하는 최소 값을 구하기 위해 최대 값이 필요한 경우가 있기 때문이다.


코드 보기


I. Coins on a Ring


최종적으로 동전 사이의 거리는 $\frac{N}{M}$이다. 그리고 동전들의 상대적 위치는 처음 입력으로 주어지는 것과 다르지 않다. 이 점을 이용해 각 동전들의 Scale을 모두 갖게 만들자. 여러 가지 방법이 있겠지만 그 중 하나로는 동전들의 위치 $\{P_i\}$ 들을 정렬하고 $P'_i = (P_i - \frac{N}{M} \times i + N) \mod N$ 으로 치환하는 방법이 있다. 동전들의 Scale이 모두 같아졌으니 새로운 위치 $\{P'_i\}$에 대해 한 지점으로 동전들을 모으는 문제로 바뀐다.


코드 보기


J. Alien Abduction Again


전형적인 Segment Tree를 이용하는 문제다. $x^3$항, $x^2$항, $x$항과 상수항에 있는 계수를 독립적이게 생각할 수 있으므로 Segment Tree의 각 노드 안에 4개의 값이 있다고 보면 된다. 나머지 연산에 유의하자.


코드 보기



댓글
댓글쓰기 폼