14959번: Slot Machines - KMP N개의 수들이 주어질 때, 이 수열은 처음 K개의 원소를 제외하고 주기 P를 갖는다.이 때, K+P가 최소가 되는, 같다면 P가 최소가 되는 K와 P를 출력하는 문제이다. 주기를 찾는 문제는 KMP에서 광고문제로 설명한 적이 있다.문자열을 이루고 있는 최소의 주기를 구하는 방법은 문자열의 길이가 S일 때, S - pi[S-1]이다.이를 이용하려면 먼저 pi배열을 구하여야 한다.pi[i] = N[...i]의 접미사도 되고 접두사도 되는 문자열의 최대 길이로주기가 시작되는 부분을 알 수 없으므로 모든 N에 대하여 확인해봐야하므로 시간복잡도가 O(N^2)이다.그러나 여기서 N개의 수를 뒤집어서 생각한다면 주기의 시작부분은 처음부터가 되게 되며단 한번의 pi배열..
14955번: How Many to Be Happy? - 최소 컷 N개의 정점과 M개의 간선으로 이루어진 그래프에서 각 간선이 MST가 포함되기 위해제거해야하는 간선의 최소 개수의 합을 구하는 문제이다. 접근 방법은 다음과 같다.u와 v를 잇는 가중치가 c인 간선이 있을 때 이 때 이 간선이 MST가 아니라는 것은가중치가 c미만인 간선들로 u와 v가 이어져 있다는 것이다.이제 이 간선을 MST에 포함되게 하려면 가중치가 c미만인 간선들로 u와 v가 이어져있지 않게 해야한다는 뜻이 되며이는 각각의 간선을 용량이 1인 간선으로 보았을 때가장 작은 유량으로 u와 v가 각각 다른 집합에 속하도록 나누는, 즉 최소 컷을 구하는 문제가 된다. 매 간선을 보며 그 간선의 비용보다 작은 간선으로만 용량이 1인 간선으로..
13560번: 축구게임 - 탐욕법 하나의 팀은 다른 모든 팀과 정확히 한 번씩만 경기를 하고 무승부는 없을 때의 팀별 승수가 주어졌을 때유효한 조합인 지 파악하는 문제이다. O(N)에 푸는 방법은 아래와 같다. Fulkerson Chen Anstee theorem: i는 1부터 N까지 일 때, ΣA[i] ≤ i*(i-1)/2 이며, ΣA[i] = N*(N-1)/2 이여야한다. 위를 만족할 경우 1, 아닐 경우 -1을 출력해주면 되는 문제이다. 또한 탐욕법으로 O(N^2)에 풀 수도 있는데매 단계마다 승수가 가장 높은 팀은 승수가 낮은 팀에 대해 이긴다라는 방법을 선택하여모든 팀에 대하여 진행해주면 풀 수 있는 문제이다.