Q

1. 빈 줄값 구하기

가장 큰 노노그램의 크기 N = 3

• 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

묶음(outlined region)의 칸 값 합 M = 24

• 20묶음이고, 가장 작은 묶음은 8칸

• 가장 작은 묶음의 값은 최대 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이 들어가야 함

빈 줄값 구하고 빈칸 채우기

• 20 * M에 이미 구해진 줄값을 빼면 됨

2. 칠하기

3블록은 2~3개

• 3블록 내 값의 합은 3 * 9 * 5 = 135이므로 최대 3개 (20 * M = 480을 넘지 않는 선)
• (3블록, 2블록, 1블록) 개수를 표시하면 (3, 1, 3) 이나 (3, 0, 15) 등이 가능
• 3블록이 2개라면 (2, 5, 2), (2, 4, 10), .. 이 가능

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이므로 바로 칠할 수 있음
      • 이후는 엑셀을 활용해, 적당히 경우를 재 가며 모두 완성할 수 있음