문제

풀이

17 * 17
열(가로줄), 행(세로줄) 중 둘의 값이 비긴 했지만, 그래도 적어도 하나의 값은 N * N * 3 이상이어야 함
- F모양이 연달은 세 블록을 사용하기 때문
가장 큰 값이 49이므로 N\le 4
N = 4라면 값이 4 * 4 * 3 = 48 이상인 줄이 연달아 4줄이 있어야 함
- 그러나 48 이상은 한 줄뿐
- 따라서 N\ne 4
비둘기집의 원리에 의해 N >= \ceil(49 / 17) = 3
따라서 N = 3

가장 작은 묶음의 값은 최대 8 * N = 8 * 3 = 24
빈 열(列)값 빼고 열의 합이 441, 빈 행값 빼고 행의 합이 458
빈 열값은 최대 17 * N = 51
전체 칸의 합 = 열값 총합 = 행값 총합 = 모든 묶음의 값의 합 = 20 * M
따라서 20 * M은 최대 492, 최소 458
23\le M\le 24
M = 23이면 빈 행값이 2라는 소린데, 이는 불가능
- 값이 빈 행이 크기 8짜리 묶음을 거쳐가기 때문
- 빈 행값이 2라면, 값이 1인 칸이 2개인 것
  - 값이 2인 칸은 둘이 짝으로 붙어 다니므로 한 줄에 하나만 있을 수는 없음
- 8짜리 묶음에 값이 1인 칸이 있다면 나머지 모든 칸이 최대값인 3이더라도 합이 22 < 23, 즉 불가능
따라서 M = 24
M = 24이므로 8칸짜리 묶음에는 모조리 3이 들어가야 함

이미 3이 확실한 칸들을 보자
49 = 3 * 15 + 2 * 2만 가능
- 2개의 2 / 15개의 3으로 끊겨야 한다
- 2개의 2는 붙어 있고, 15개의 3은 3개씩 붙어 있어야 한다
- 아래에서 6번째, 7번째 칸은 2가 될 수 없다 (3이 위 10개, 아래 5개로 끊김)
- 따라서 아래에서 6번째, 7번째 칸은 칠해 준다
모양을 토대로 3블록 2개가 있을 법한 위치를 잡아 준다
- 이제 더 이상 3블록이 들어갈 수 없다. 3블록은 2개.
- (2, 5, 2)도 불가능. 1짜리 F가 2개뿐일 수가 없다.
  - 맨 윗렬의 경우 14 - 3 * 3 이 홀수이므로 1짜리 F가 걸쳐야 한다
  - 값이 22인 열과 20인 맨 아랫열도 마찬가지
  - 따라서 1짜리 F는 3개 이상 필요
- (2, 4, 10)이 가장 가능성 높음
- (2, 3, 18)이면 총 240칸 필요. 289칸 중 49칸만 빈칸이려면 F들이 촘촘하게 들어가야 함
- (2, 2, 26)이면 총 260칸 필요. 여기서부터는 거의 불가능해 보임
- (2, 4, 10)으로 생각하고 2개짜리 블록을 잘 배치
  - 값이 49인 행과 43일 열에서부터 출발
    - 49 = 3 * 15 + 2 * 2, 43 = 3 * 9 + 2 * 8이므로 바로 칠할 수 있음
    - 이후는 엑셀을 활용해, 적당히 경우를 재 가며 모두 완성할 수 있음