음.. 밑에 너무 깔끔한 풀이가 있어서 쓰긴 그렇지만..

원래 고등학생의 문제고, 고등학생에 맞는 풀이를 쓴다는 점에서 적어본다.


고등학교 때, 조합 문제를 푸는 내 마인드는 다음과 같았다.


0. 주어진 경우보다 좀 더 작은 경우를 생각해보고 일반화가 가능한가 보자.

1. 기발한 풀이가 떠오르지 않으면 그냥 경우를 '잘' 나눠서 세라.

2. 셀 때는 경우끼리 겹치지 않게 세고, 실수하지 마라.

3. 분명히 고등학교 과정 내에서 답이 있을테니 거기서 찾아보자.


일단 블록에 번호를 매기자.


1) 2) 3) 4)

5) 6) 7)

8) 9)

0)


일단 1) 2) 5)만 있는 경우를 고려해보자.

그러면 1)에 1이 들어가는 경우 9개, 2가 들어가는 경우 4개, 3이 들어가는 경우가 1개다.

이렇게 작은 경우도 1)에 들어가는 경우의 수에 따라서 나눠야되니까 0은 거의 불가능하다.

하지만 여기서 작은 힌트를 얻을 수 있는데,


1. 1)의 숫자가 결정되면 2), 5)는 결정하기가 쉽다는 것.

2. 작은걸 구해보는건 크게 도움이 안 된다는 것;;


그래서 좀 귀찮음을 감수한 내 풀이는 다음과 같다.

1. 1)에 1, 2, 3을 채운다. (3을 채우면 자동적으로 경우가 하나가 된다.)

2. 3), 6), 8)에 가능한 모든 경우의 수를 채운다.

3. 2), 5), 4), 7), 9), 0)을 결정한다.


예를 들어 3), 6), 8)에 들어가는 숫자가 1, 2, 2라면

2)는 1, 2의 2가지, 5는 1의 1가지, 4), 7), 9)는 2, 3의 2가지, 0)은 1, 2, 3의 3가지이므로

총 48개의 경우의 수 x 2(2, 1, 1이면 대칭이니까)해서 96가지를 뽑아낸다.


1)에 1을 넣고 3), 6), 8)에 1-3인 경우의 수는 27개인데, 9개는 대칭으로 구할 수 있으므로 18가지 경우,


viewimage.php?id=20bcc42e&no=24b0d769e1d32ca73cee83fa11d02831a8a865d070dfb053de17d9bb368b24fd428c3183cc5bfe134c99fc85e7573f484f614b95323eedd60d1c63


1)에 2를 넣고 3), 6), 8)에 2-3인 경우의 수는 8개인데, 2개는 대칭으로 구할 수 있으므로 6가지 경우,


viewimage.php?id=20bcc42e&no=24b0d769e1d32ca73cee83fa11d02831a8a865d070dfb053de17d9bb368b24fd428c3183cc5bfe134c99fc85e7573f4848651ec23369e0d60d1c63

1)에 3을 넣으면 단 하나의 경우의 수가 나온다.


사실 이 글은 봤는데, 토요일 전체가 학회였고, 다른 퍼즐 문제를 푸느라 이 문제에 신경을 안 쓰고 있었다.

내가 풀었던 문제는


8x8 체스판을 L-테트라미노(그러니까 테트리스 L블록의 8가지 경우) 15개와 2x2 정사각형 블록 1개로 채울 수 있는가?


였는데, 조합 문제는 저렇게 길게 썼어도, 내가 올린 사진이 풀이의 전부고 10분 정도 걸렸는데,

이 체스판 문제는 최소 30분 넘게 걸렸다.. 좋은 풀이 있으면 알려줘 얘들아