부분합. [25682]

[1. 문제 설명]

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

---

[2. 풀이 접근]

 

완전 탐색

• 모든 구간에 대해서, 색칠해야 할 개수를 확인 후 최소값을 업데이트 해나가는 방법
• 위 방식은 3중 for 문을 유도하며, N, M, K 가 최대 2000 까지이므로, 1초 안에 계산하기 어려움,
• 그러나, 모든 구간에 대해서는 확인 해봐야 함.
  # 어떤 구간이 최소가 될지는 알 수 없기 때문,
• 즉, 특정 구간에 대해서 (crop? 한 영역) 에서 몇번 색칠 할 지를 logn 이하로 확인 할 수 있어야 한다.

결과의 특성

• 문제 조건 상, K*K 로 잘라내고, 색칠한 형태는 아래와 같은 두가지 구조만 갖는다.
• (y, x) = (1, 1) 위치가 검정색인 경우 => Case A
• (y, x) = (1, 1) 위치가 흰색인 경우 => Case B
• 여기서, 전체 체스판을 Case A 와 Case B 같은 형태로 만든다면,
• 전체 체스판 중 어디를 잘라도 최종적으로 원하는 형태와 같은 형태를 갖게 된다.
• 그래서, 전체 체스판을 Case A 와 같은 형태로 만들 때 각 위치에서 색칠되어야 할 위치를 먼저 확인 할 수 있다.
• Case B 도 마찬가지,

부분 합

• 그래서 전체 체스판에서 Case A 혹은 Case B 로 만들 때,
• 각 위치에 0(색칠하지 않음) , 1(색칠 함) 설정 할 수 있고
• 이 2차원 배열을 이용하여 K*K 로 잘라내었을 때,
• 얼마나 색칠 할지를 부분 합을 이용하여 상수시간안에 알아 낼 수 있다.
• 물론 결과는, Case A 와 Case B 모두 확인하여 둘 중 최소를 선택하도록 해야 한다.

---

[3. 코드]