주간 문제풀이 04 (BOJ 20188 / 5561 / 10227 / 20189 /20190)

P5 - 등산 마니아

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

20188번: 등산 마니아

문제: 트리가 주어지고, 어떤 두 노드 사이의 “다양성”을 두 노드 사이의 트리 루트를 거치는 최단경로로 정의한다. 모든 가능한 노드 쌍의 다양성의 총 합을 계산하자.

 

풀이:

각 간선이 최종 답에 공헌하는 값을 구하는 법을 생각해보자. 즉, 각 간선에 대해 해당 간선을 최단경로에서 거치는 노드 쌍 개수를 세는 것이다.

 

해당 값은 간선 아래에 있는 subtree의 크기만 알면 쉽게 구할 수 있다. 아래 그림을 예시로 들면, 빨간색 간선이 최종 답에 공헌하는 값은 "파란색 원 안에서 노드를 두 개 고른 노드쌍" + 파란색과 초록색 원 안에서 노드를 각각 하나 고른 노드쌍" 의 개수와 같기 때문이다.

각 간선 아래에 있는 subtree 개수는 dfs를 돌면서 구할 수 있다.

코드: http://boj.kr/84829cf6c12e418d964a6e3397d3e133

 

 

P4 - 과자의 분할

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

5561번: 과자의 분할

문제: 길이가 N(<=1e4)인 막대 모양 과자가 있고, 길이 1마다 있는 각 지점을 자르는데 필요한 힘이 정수로 주어진다. 과자를 N/2 길이인 두 묶음으로 나눌 수 있도록 자르는 데 필요한 최소 힘의 합을 구하자. 

 

풀이:

먼저 간단한 관찰 하나만 짚고 넘어가자.

- 특정 위치에서 과자를 분할한다면, 그 분할한 위치의 양쪽 조각은 서로 다른 사람에게 나눠줘야 한다. (같은 사람한테 줄거면 자를 이유가 없다)

그러면 다 자른 후의 첫번째 조각은 A한테, 두번째 조각은 B한테, 세번째 조각은 A한테.. 이런 식으로 A와 B한테 번갈아가며 주게 된다.

 

이제 이걸 이용해서 dp로 풀어보자. "dp[i][j] = 길이 i까지 봤고, 현재 보고 있는 조각을 받게 될 사람이 총 합 길이 j의 과자를 가지고 있을 때의 최소 힘의 합"으로 정의하면, 아래와 같이 점화식을 세울 수 있다.

dp[i+1][j+1] = dp[i][j] (안잘랐을 때는 내가 보고 있는 조각이 길이 1 늘어난다)

dp[i+1][i-j+1] = dp[i][j] + arr[i] (잘랐을 때는 내가 보고 있는 조각을 받게 될 사람이 바뀌면서, j값을 i-j와 같이 반전시켜야 한다)

 

N^2 메모리는 메모리 초과가 나기 때문에, 바로 전 행의 dp값만 가지고 있도록 메모리 최적화를 해야 한다는 점에 유의하자.

풀이: http://boj.kr/887d6c47e7414a4eb5eb1cfde9054b56

 

P3 - 삶의 질

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

10227번: 삶의 질

문제: R*C 격자 위에 서로 다른 숫자들이 적혀있다. 이 격자 위의 모든 가능한 H*W 크기의 영역들 중에서, 가장 작은 중간값을 가진 영역을 찾아라.

 

풀이:

중간값을 직접적으로 쿼리하는 것은 어려우니, 생각을 조금 틀어서 특정 블록 안에 x보다 작거나 같은 수가 정확히 (H*W+1)/2개 있으면 x가 중간값이라고 생각해 보자.

 

이렇게 생각하게 되면 "특정 수 x보다 작거나 같은 중간값이 있는가?" 라는 결정문제를, x보다 작거나 같은 수들만 남겨놓은 격자 위에서 수가 (H*W+1)/2 개 이상이 있는 H*W 영역이 있는지 세는 방식으로 대답할 수 있다. 이는 x보다 작거나 같은 수들만 남겨놓은 격자 위에서 누적합을 구해놓고, 모든 H*W영역 각각에 대해서 O(1)에 영역 내의 수 개수를 세는 방식으로 풀 수 있다. 이는 O(RC)에 풀린다.

 

이 결정문제를 log(RC)번 반복하면 가능한 가장 작은 중간값을 구할 수 있고, 최종 복잡도는 O(RClog(RC)) 이다.

 

코드: https://www.acmicpc.net/source/share/70df2644374c4057a13544e054645b79

P2 - 사탕 돌리기

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

20189번: 사탕 돌리기

문제: 깡통 N개에 각각 사탕이 K개 들어 있다. 사탕에는 1~N사이의 색깔이 있고, 각 색깔의 사탕은 정확히 K개 있다. “사탕 돌리기” 연산은 i번 깡통에서 (i+1)%N번 깡통으로 사탕을 정확히 하나씩 순서대로 옮기는 연산인데, “사탕 돌리기”를 정확히 Q번 수행해서, i번 깡통에 i번색깔의 사탕만이 존재하는 “올바른 상태”로 만들 수 있는지 구하자. 

 

풀이:

바로 떠오를 만한 풀이는: 각 숫자가 올바른 위치까지 가기 위해서 필요한 거리의 합을 구할 수 있다. 사탕 돌리기 연산 한 번에 정확히 이 거리를 N 줄일 수 있고, 따라서 거리의 합 / N이 Q보다 작거나 같으면 가능하다고 판정한다. (거리의 합은 무조건 N으로 나누어 떨어진다.)

이 풀이에는 엣지 케이스가 하나 있는데, 이는 1번 깡통에 있는 사탕을 무조건 먼저 움직여야 함에서 온다. 아래 두 케이스를 고려해보자.

```

4 1 1
1
4
3
2

----

4 1 1
3
2
1
4

```

두 케이스 모두 거리의 합은 4로 같지만, 첫 케이스에서는 무조건 올바른 자리에 있는 1을 움직여야 하기 때문에 실질적으로 옮겨야 할 거리는 8이 된다. 반면에 두번째 케이스에서는 3을 무조건 움직여야 하지만, 어처피 3이 틀린 자리에 있었음으로 움직여야 하는 총 거리에는 영향이 없다. 즉, 1번 깡통에 있는 사탕이 모두 올바른데 올바르지 않은 깡통이 존재하는 경우에만 움직여야 할 거리에 N을 더해서 생각하면 된다.

 

몇 가지 주의해야 할 사항이 있다. (=내가 풀면서 놓친 사항..)

- 문제를 잘못 이해하면 자칫 사탕 돌리기 연산이 각 깡통에서 사탕을 하나씩 골라 거리 1의 rotation을 수행하는 것이라고 생각할 수 있다. 다만 1번깡통 -> 2번깡통으로 옮긴 이후에 2번깡통 -> 3번깡통으로 옮기기 때문에, 2번 깡통에 처음에 있는 것을 3번 깡통에 옮기는 대신 1번깡통에서 옮겨온 것을 바로 3번으로 옮길 수도 있다. 때문에 그냥 rotation과는 좀 다르다.

- 거리의 합은 int를 넘어설 수 있다. 오버플로우에 유의하자.

 

P1 - 버블버블

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

20190번: 버블버블

문제: 배열 A를 정렬하기 위해서 최소 몇 번 인접한 수를 교환해야 하는지 셀 수 있다. 배열 A가 주어졌을 때, 모든 i에 대해서 A_i를 임의의 수로 바꾸었을 때 정렬에 필요한 최소 교환 횟수를 구하자.

풀이:

먼저, 아래 관찰이 필요하다.

- "정렬에 필요한 최소 교환 횟수" 는 배열의 inversion개수(i < j, a_i > a_j 인 i, j pair 개수) 이다.

-  다른 임의의 수로 바꾸는 연산에서, 기존에 주어진 수 중에서 하나로 업데이트하기만 하면 최소 교환횟수를 얻을 수 있다.

 

첫 번째 관찰에서부터, 우리는 각 수를 바꿀 때 inversion의 개수를 최소화하는 방향으로 바꿔야 한다는 것을 알 수 있다. 그러면 우리는 수를 왼쪽부터 오른쪽으로 순회하면서, i번째 수를 보고 있을 때 "a_i를 t로 업데이트하면, 이 수로 인해 발생하는 inversion 개수"를 모든 t에 대해 조회할 수 있는 세그먼트 트리를 관리하는 것을 생각해볼 수 있다.(두번째 관찰로 인해, 세그먼트 트리에서는 입력에서 주어진 수만 고려해도 된다)  여기서 "이 수로 인해 발생하는 inversion 개수"를 정확히 정의하자면: "이 수보다 앞에 있지만 더 큰 수의 개수 + 이 수보다 뒤에 있지만 더 작은 수의 개수"이다.

 

이러한 세그먼트 트리를 관리할 수 있으면 각 위치에 대해 해당 위치의 수를 최소한의 inversion이 있도록 교체했을 때 몇 번의 inversion이 발생하는지 구할 수 있고, 더 나아가 inversion을 기존과 비교해 몇 번 줄일 수 있는지를 구하면 답이 나온다.

 

이 세그먼트 트리를 관리하는 법을 조금 더 설명하자면, 맨 앞의 수를 볼 때는 각 입력된 수 a_i가 모두 뒤에 있음으로, 내가 보고 있는 맨 앞의 수가 [0, a_i)까지의 수로 업데이트되었을 때 inversion이 1회 발생한다. 그렇기 때문에 최초에 [0, a_i) 구간에 +1을 해준다. 다음 수로 넘어가는 시점에서는, 원래 보고 있었던 수는 뒤에서 앞으로 위치가 바뀐다. 즉 원래는 그 숫자보다 커야 inversion이 발생했지만 이제는 작아야 inversion이 발생함으로, [0, a_i) 구간에 대해 -1 업데이트, (a_i, MAX] 에 대해서 +1 업데이트를 해주면 된다. 여기서는 업데이트 시점을 엄밀하게 설명하지는 않았지만, 대략 이런 식으로 inversion을 유발하는 구간에 대해 range increment를 하면 된다. 쿼리할 때는 최소한의 inversion이 있을 때를 찾으면 되어서 range min query가 필요하다. 즉 lazy segtree를 쓰면 된다.

 

세그 구현은 https://codeforces.com/blog/entry/18051 를 참고하면 좋다. 이 글의 "Increment modifications, queries for maximum"과 거의 똑같이 짜면 된다.

참고: https://cp-algorithms.com/data_structures/segment_tree.html

 

코드: http://boj.kr/16f5fc43b66d4c5090846de1acd7aed6

 

 

TMI

어떻게 하면 "더보기" 란의 배경색을 회색으로 만들 수 있을까?

```html

<style>
  .moreless-content {
    background-color: #f5f5f5;
  }
</style>

```

이걸 html모드에서 적어두어도, 기본모드로 저장하면 없어진다.