[백준] 33151. 마슈 반데드와 마법사의 격자판

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

문제요약

• N x N 격자판에 두칸 동전개수의 차이는 정확히 1이 되도록 총 K개의 동전 배치
• N : 1000, K : 10^9

접근법

• 처음 문제를 접하면 난감하다. 단서를 하나씩 찾는다.
• 인접한 칸과의 차이는 +1 또는 -1 => (홀,짝) 또는 (짝,홀)
• N이 짝수이면 홀,짝,홀,짝,..... 의 합이 짝수여야함 => K가 홀수이면 안됨
• N이 홀수일때
  • K가 홀수이면 첫 칸이 홀수여야함
  • K가 짝수이면 첫 칸이 짝수여야함
  • N이 3일때 예시
  • 홀 짝 홀 | 짝 홀 짝
  • 짝 홀 짝 | 홀 짝 홀
  • 홀 짝 홀 | 짝 홀 짝
• 최소한으로 필요한 동전이 있을까? => 있음
  • N이 2일때 => 최소 2개
  • N이 3일때 => 최소 4개
  • 0 1 0
  • 1 0 1
  • 0 1 0
• 최소한으로 배치한 상태에서 2개씩 추가해도 조건을 만족할까 => 만족
  • 0 1 0 => 2 1 0 => 2 1 2 ... 2 1 2 => 2 3 2 ...
  • 1 0 1 => 1 0 1 => 1 0 1 ... 1 2 1 => 1 2 1 ...
  • 0 1 0 => 0 1 0 => 0 1 0 ... 2 1 2 => 2 1 2 ...
• 즉 최소한의 동전 개수를 만족하면 배치가 항상 가능하다.
  • 기본적으로 1을 배치하고 (N이 홀수일때는 K의 홀/짝에 따라 첫 값을 0, 1로할지 결정)
  • 전체를 +2로 몇 번 가능한지 판단한다. (N x N x 2를 몇 번 할 수 있는지)
  • 그리고 동전이 남으면 작은 숫자들을 +2를 한다.
  • 그래도 동전이 남으면 또 작은 숫자들을 +2한다.