백준 8131 Ploughing (POI 2005/2006)

Ploughing

8131번: Ploughing

 

최대 골드 정도의 사전지식 만으로 풀 수 있는 다이아 3 문제이다.

 

상당히 흥미롭다.

 

이 문제도 풀이가 다양한 것 같다.

 

아 그리고 TL이 많이 빡빡하다.

---

목차
1. 문제 요약
2. 발상
3. 풀이
4. 코드

---

1. 문제 요약

2000 × 2000 숫자 배열이 있다.

한 번에 바깥쪽 4개의 변 중 하나를 골라서 지운다. (즉 오른쪽 끝, 왼쪽  끝, 위쪽 끝, 아래쪽 끝 변 중 하나)

- 이 때 지우는 수들의 합이 K 이하여야 한다.

전부 지우는 횟수의 최소값은?

(지울 수 있음이 보장된다.)

K = 12 인 경우 최소 8회

2. 발상

처음엔 parametric search 인 줄 알았는데, 그건 개같이 아니었다.

 

1.

한 번 작업마다 가로 혹은 세로를 택하게 된다.

모두 지우려면, 어쨌든 가로줄을 모두 한번씩 택하거나, 세로줄을 모두 한번씩 택해야만 한다.

 

편의상 가로줄을 모두 택하는 경우만 생각하자. (배열 돌려서 똑같이 한 번 더 풀어주면 됨)

2.

그러면 세로줄을 최소한의 횟수로 선택해서 모두 없앨 수 있어야 한다.

이 때 세로줄을 어디까지 선택할 것이냐를 정해두면 삶이 편해질 것 같다.

참고로 당연히 왼쪽, 오른쪽 끝에서부터 차례대로 선택해야 되기 때문에 경우의 수는 $_{M}C_{2}$ 가지가 있다.

 

근데 그걸 정하면 이제 진짜로 다 없앨 수 있는가를 체크해야 한다.

그것도 쉽진 않지만 일단 못해도 O(N+M) 이 걸릴 것 같다.

 

즉 총 $\mathcal{O}(M^{2}(N+M))$ 이므로 세제곱이 걸린다. 망했다.

3.

근데 잘 생각해보면 세로줄을 왼쪽에서 어디까지 지우자 를 결정하면 반대쪽은 자동결정이다.

 

이것은 가로줄을 모두 지울 수 있다 와 (남은) 가로줄의 숫자 합이 전부 K 이하 인 것이 동치이기 때문이다.

즉 가로줄들이 전부 합 K 이하가 되도록 세로줄을 오른쪽에서 최소한으로 선택해주면 된다. (우리는 최소값을 찾는 거니까) 

이해를 돕기 위한 그림

예를 들어, 우리가 세로줄을 "왼쪽에서 2개 지우자" 라고 결정했다. 그러면 세로줄을 "오른쪽에서는 2개 지워"야 한다.

1개만 지우면 가로줄만 선택해서는 절대 전부 없앨 수 없다. (합이 K 초과이므로)

3개 지울 수도 있겠지만, 우리는 최소 횟수를 알고 싶기 때문에 굳이 하나 더 지울 필요가 없다.

덧붙여서 오른쪽에서 2개 지우는 경우가 (나중에 되는지 체크해보니까) 불가능하다면 3개 지우는 건 당연히 불가능하다.

(포함 관계니까 자명하게도...)

 

세로줄을 어디까지 지울 것이냐 를 M 가지 경우로 줄였다.

 

이제 우리가 고른 범위 내에서 진짜 다 없앨 수 있는지를 O(N+M)에만 판별해주면 된다.

즉 세로줄을 왼쪽에서는 x번, 오른쪽에서는 y번 선택한다고 할 때 다 없앨 수 있는지 판단하면 된다.

4.

사실, 어느 변을 몇 번 선택하는 지 결정되어 있다면, 그걸 직접 $\mathcal{O}(N+M)$ 시간에 해보는건 쉽다.

 

왜냐하면 어떤 변을 지울 수 있다면 즉시 지우는게 greedy하게 좋기 때문이다.

그걸 안지우고 기다리는게 더 좋을지 고민할 필요가 없다.

 

어차피 각각 변을 몇 번 선택하는지 결정되어 있기 때문에, 바로바로 지워줘서 변의 합을 줄이는게 낫다.

각 변의 합은 prefix sum으로 O(1)에 알 수 있고, 최대 N+M 번 지우면 모두 지워지기 때문에 시뮬레이션 해주면 된다.

 

3. 풀이

참고로 발상 3 에서 오른쪽에서 지울 개수를 자동결정하는게 쉽지는 않다.

 

 

1. 세로, 가로 방향에 대해 prefix sum 계산

 

2. 발상 3 에서 자동결정되는 개수를 전처리로 구해준다.

즉 각 가로줄에 대하여 합이 K 이하가 되기 위하여 "왼쪽에서 i개 지울" 때 "오른쪽에서 몇개 지워"야 하는지 모두 구해준다.

-- 이걸 이분탐색으로 하면 TLE 뜨고, 투포인터로 해주면 된다. (합이 K이하일 때까지 오른쪽으로 가주는)

 

3. "세로줄을 왼쪽에서 i개 지울" 때 가능한지 판단해준다.

각 가로줄마다 전처리해놓은게 있기 때문에 그들 중 (개수의) 최대값을 구해서 그만큼 오른쪽에서 지워야 한다.

 

4. 입력 배열을 돌려서 1~3 반복

 

4. 코드

https://www.acmicpc.net/source/52136087

 

난좀 더럽게 구현한 것 같아서 올리긴 부끄럽다.