씹덕은 특이점의 꿈을 꾸는가?

https://www.acmicpc.net/problem/11873

https://6epsilon.tistory.com/14

에서 만들었던, 각 행에서 각 위치에 대해 위로 연속한 1의 개수를 구한다. 이제 각각의 줄에서 히스토그램에서 가장 큰 직사각형을 찾는 유명한 문제를 풀면 된다. 그러면 이 부분의 구현에 따라 O(nmlogm)이나 O(m)에 처리할수 있다. 

https://www.acmicpc.net/problem/1733

백준 13361 최고인 대장장이 토르비욘을 풀었던 기억이 나서, 초기 접근 자체는 쉬웠다. 해당 문제는https://koosaga.com/166에 잘 정리되어있다. 

먼저, 티셔츠의 안쪽 숫자와 바깥쪽 숫자를 간선으로 잇는다. 이제 그래프에서 각각의 간선에 대해 하나씩 정점을 중복 없이 할당해 주어야 하는 문제가 된다. 그렇게 얻어진 그래프의 각 컴포넌트를 생각해보자. 

일단, 간선 개수 > 정점 개수 라면 중복 없이 할당하는게 불가능하다. 그러면 남는 경우의 수는 2가지인데, 

간선 개수 = 정점 개수 - 1 인 트리 컴포넌트가 나오거나, 간선 개수 = 정점 개수인 사이클이 하나에 트리가 뻗어나오는 그래프가 있겠다. 여기서 관찰을 하나 할 수 있는데, 트리에서의 리프 노드, 즉 이어진 간선이 1개인 정점은 무조건 그 이어진 간선에 해당 정점을 할당해주는 식으로 컴포넌트의 크기를 줄여나갈 수 있다. 정점 개수와 간선 개수가 모두 1씩 감소하기에, 이렇게 해도 여전히 문제 해결이 가능한 컴포넌트가 남는다. 

이 컴포넌트의 크기를 줄여나가는 과정은 위상정렬의 아이디어를 빌릴 것이다. 이어진 간선이 1개인 점들을 다 큐에 넣고, 하나하나 pop하면서 그 정점을 제거했을 때 새로 생기는 간선이 1개인 점들을 추가해 주자. 더 이상 큐에 값이 남지 않을 때까지 돌려주면, 트리 컴포넌트의 간선들에는 정점 할당이 끝날 것이고, 간선 개수 = 정점 개수인 컴포넌트에는 사이클 하나가 남을 것이다. 

https://6epsilon.tistory.com/10

위상정렬 과정만 보면 이 문제와도 비슷하다. 

남은 사이클에서는 DFS같은 방법으로 한 바퀴를 돌면서 간선과 정점을 매칭해주면 된다. 각각의 간선들에 전부 시계방향의 정점을 할당하거나, 전부 반시계방향의 정점을 할당할 방법이 있으면 된다.

사실, 토르비욘 생각나자마자 유니언파인드로 코드를 짜다가, 위의 문제를 해결하는 코드를 짜면 결국 필요없어진다는걸 깨달았다. 불가능 판별도 해결하는 과정에서 확인할 수 있었다. 마지막에 남는게 하나의 사이클인지만 확인해주면 되기 때문. 

https://www.acmicpc.net/problem/25257

몬티 홀 문제는 상당히 유명하므로, 바꾸는게 무조건 이득이다 정도는 다들 알고 있을 것이다. 

이 문제는 몬티 홀 문제를 일반화한 것으로, 전체 문 D개가 있고 문 하나에 보물이 있을 때, S개의 문을 처음에 고르면, 나머지 D-S개의 문 중 E개를 열어 보물이 없음을 알려 준다. 이 때 고르는 문을 바꾸어 얻을 수 있는 최대 확률을 물어본다. 

문제 상황을 순서대로 생각해 보자. 

먼저 S개를 고르면, 고른 문 각각에 보물이 있을 확률은 1/D이고, 고르지 않은 문 중 보물이 있을 확률은 D-S/D이다.

여기서, E개의 문을 열면 D-S-E개의 문에 이 확률이 나눠지게 되고, (고르지 않은 문 중에 보물이 있을 확률이 D-S/D임이 유지되어야 하기 때문) 고르지 않은 문 중 열리지 않은 문 D-S-E개에 보물이 있을 확률은 각각 D-S/D(D-S-E)이다. 

마지막으로 S<=D-S-E 이면 D-S-E 개중 S개를 고르면 되므로 답은 S(D-S)/D(D-S-E),

S>D-S-E일 경우 D-S-E개의 문을 모두 고르고 확률이 1/D인 문 2S+E-D개를 고르면 D-S/D + (2S+E-D)/D = S+E/D 가 답이다. 

https://www.acmicpc.net/problem/14458

초기 상태의 가로지르는 쌍은, inversion counting이므로 nlogn에 처리할 수 있다.

세그트리나 BIT, 또는 병합 정렬로 구현할 수 있다. 

그러면 초기 상태가 아닌, k개를 옮긴 상황은 어떻게 생각해야 할까?

아이디어만 설명할 것이기 때문에, 편의상 왼쪽의 목초지는 1...N이라고 두자.

또, 마지막 n-k개를 옮기는 상황이나 처음의 k개를 옮기는 상황이나 같은데, 이제 맨 앞의 목초지를 맨 뒤로 보내는 걸 반복하며 가로지르는 쌍의 개수를 업데이트하면 된다고 생각해 볼 수 있다. 

그림에서는, 1을 맨 뒤로 보냈을 때, 3,4,5와의 가로지르는 쌍은 사라지고, 2와 가로지르는 쌍이 새로 생긴다. 즉, 1이 오른쪽에서 4번째이므로, 1보다 앞에 오는 3개와의 쌍이 사라지고, 1보다 뒤에 오는 1개와 쌍이 생겼음을 쉽게 관찰할 수 있다.

1을 포함하지 않는 쌍에는 당연히 영향을 주지 않는다. 

왼쪽에서 맨 앞에 올 경우 오른쪽에서 자기보다 앞인 숫자 Index-1개와 항상 Inversion을 형성하고, 왼쪽에서 맨 뒤에 올 경우 오른쪽에서 자기보다 뒤인 숫자 N-index개와 항상 Inversion을 형성한다는 점을 활용하는 것이다.

즉, 각각의 업데이트에서 Index-1개의 Inversion이 해체되고, N-index개의 Inversion이 생긴다. 

Index는 잘 저장하면 O(1)에 접근이 가능하기에, O(1)에 inversion의 수를 업데이트할 수 있다. 한 바퀴 돌면서 왼쪽과 오른쪽에 대해 수행해 보면 O(n)에 가능한 상황을 전부 확인할 수 있다.

한번 더 적용하면 4개의 Inversion이 해체되어 최소가 된다. 이는 문제에서 주어진 TC와도 같은 형태이다. 

PS. 왼쪽과 오른쪽 중 하나만 하면 안된다는 걸 직관적으로는 알겠는데, 반례 찾기가 귀찮다. 알면 제보 부탁드린다.

https://www.acmicpc.net/problem/6101

먼저 DP를 하는데, DP[i]를 i번째까지를 적절히 그룹을 나눠서 얻을 수 있는 비용의 최소값이라고 가정하자. 

그러면 DP[i]를 업데이트 할 때, j~i까지 음식의 종류가 k가지일 때 이것들을 하나의 그룹으로 만들어 DP[i]와 DP[j-1] + k^2 의 최소값으로 업데이트하면 된다. 그리고 이 k가 √n을 넘을 경우, 하나씩 그룹으로 나누는 것보다 손해이므로, O(n√n)짜리 풀이를 생각해 볼 수 있다.

그러면, 이 각각의 k에 대해,  j~i까지 음식의 종류가 k가지가 되는 최소의 j를 잘 업데이트하면 된다. (DP는 단조증가)

i-1에서 아래와 같이 K=1,2,3 인 경우의 집합이 나타난다고 생각해 보자. 

(3), (2, 3), (1, 2, 3) 

그러면 arr[i]=1이라고 생각해 보면, i에서는 위에서의 각각의 J에 대해 집합이 

(1,3), (1,2,3), (1,2,3)이 되고, 2번째 집합인 (1,2,3)은 지우면 K=2,3 에 대해 나머지 j는 그대로 가져갈 수 있다.

k가 1인 경우는 (1)과 i를 추가하면 된다. 이부분도 빈 집합을 앞에 추가하면 각 집합에 1을 추가한 뒤 하나의 집합을 삭제하는 원래의 방식으로 처리할 수 있다. 

처음에는 이걸 관리하기 위해 집합 자체를 관리하는 Bitset을 써야 된다고 생각했고, 그걸로 AC를 받긴 했다. bitset을 선언하는 등의 시간 상수가 생각보다 작은 모양. 하지만 역시 찜찜해서, 더 생각해본 결과 필요 없다는 걸 깨달았다. 

집합에 arr[i]가 포함되기 직전인 시점, 즉 지워지는 시점이 arr[j-1] = arr[i]가 되는 시점과 같기 때문에, 이를 체크하면 집합을 굳이 저장할 필요 없이 어떤 j를 삭제해야 할지 알 수 있다. 

필자는 List를 관리했는데, 그냥 배열 관리해도 문제가 없을거 같다. 

https://www.acmicpc.net/problem/3321

n개의 행 각각에 대해 그 행을 밑변으로 하는 직사각형을 확인하면 된다. 

각 행에서 각 위치에 대해 위로 연속한 1의 개수를 위 행에서의 값을 참조하여 O(m)만에 update할 수 있다.

대충 아래와 같은 그림을 생각해 보면 되겠다. 

이 연속한 1의 개수를 내림차순으로 정렬하면, 그 행을 밑변으로 하는 직사각형 중 가장 큰걸 쉽게 확인할 수 있다. TC의 답을 나타낸 아래 그림과 같이, 내림차순인 히스토그램에서 가장 큰 직사각형을 구하는 것이기 때문이다. 

그리고 연속한 개수가 1 증가하거나 0으로 바뀌거나 둘 중 하나기에, 0으로 바뀐건 뒤쪽으로 몰아 놓으면 1이 증가하는 부분은 위 행에서의 정렬 상태가 유지되어 O(m)만에 정렬까지 처리된다. O(mlogm)으로 정렬하면 터진다. 

0.6초라서 상수가 크게 짜면 O(nm)짜리 풀이긴 하지만 TLE가 날 수 있음에 주의하자. 필자는 592ms로 통과했다.

https://www.acmicpc.net/problem/20189

제자리가 아닌 사탕이 있으면, 결국 그 사탕을 원래 자리로 옮겨줘야 하고, 그 과정을 잘 나누고 이어서 진행하면 문제가 해결될 것이라고 생각해 볼 수 있다. 특히 사탕을 옮겨 놓게 되면 그 위치는 사탕의 개수가 K+1개이므로, 제자리가 아닌 사탕이 있어 항상 그 자리에서 유의미한 이동을 이어 나갈 수 있음을 확인할 수 있다. 제자리에 가져다 놓은 사탕은 더 이상 이동할 일이 없다는 것이다. 

한 바퀴가 돌면, 제자리가 현재 위치보다 앞쪽인 사탕의 개수가 하나 줄어들게 되고, 유의미한 이동이 보장되어 바퀴의 수와 그 사탕의 개수가 같음이 보장되므로 그 개수만 세 주면 문제가 해결된다. 

하지만 1번 자리는 위의 공식이 적용될 수 없어 무의미한 이동이 발생할 가능성이 있으며, 처음 주어진 상태에 1번 자리가 완성돼 있으면 이를 해소하기 위해 1을 옮기고 다시 가져오는 한번의 이동이 추가로 필요하다. 이를 체크해 주면 문제를 해결할 수 있다. 

https://www.acmicpc.net/problem/5896

그리디한 접근법을 적용할 수 있는 문제이다. 간단히는 소의 숫자가 i+1인 경우의 최적해에서 고른 소가 i인 경우의 소를 항상 포함하기에 그리디한 접근이 가능하다고 보면 되겠다.

k개의 소를 구매할 때까지는, 쿠폰을 사용한 가격 중 낮은 순서부터 고르는 것이 최적임은 자명하다. 

그 이후에는 2가지 경우가 있는데, 하나는 남은 소들 중 쿠폰을 적용하지 않았을 때 가장 싼 소를 가져가는 것이다. 

또는 쿠폰을 사용하는 소를 추가해야 하는데, 쿠폰을 사용한 소들 중 하나를 쿠폰을 사용하지 않게 바꾸고 쿠폰을 사용하는 소를 추가해야 한다. (바꾸는 소를 고르는건 비용이 최소가 되도록 Priority Queue를 이용하자.)

이렇게 바꾸지 않을 경우, 보고 있는 소를 추가하는 것보다 지금 가지고 있는 소를 유지하면서 위의 경우를 사용하는 것이 낫기 때문이다. 다시 말해, 이미 쿠폰을 사용한 A라는 소가 있다고 하자. 시장에는 A보다 쿠폰가가 낮은 소가 없기에, A를 쿠폰을 사용하던 사용하지 않던 항상 데리고 있는 상태를 유지하는 게 최적이라는 것이다. 

이제 소의 숫자를 늘려 가며 2가지 경우 중 더 사용하는 돈이 적은 걸 선택하면 된다.

(쿠폰을 사용한 소의 가격과 사용하지 않은 소의 가격을 각각 정렬해 두면 시간 내에 해결할 수 있다.)

사용한 돈이 M을 초과하지 않을 때까지 소를 추가하는 걸 반복하면 문제를 해결할 수 있다.