프로젝트 오일러 117번

Using a combination of black square tiles and oblong tiles chosen from: red tiles measuring two units, green tiles measuring three units, and blue tiles measuring four units, it is possible to tile a row measuring five units in length in exactly fifteen different ways.

How many ways can a row measuring fifty units in length be tiled?

---

길이 1인 정사각형 모양의 검은색 타일과 길이 2인 직사각형 모양의 빨간색 타일, 길이 3인 직사각형 모양의 초록색 타일, 그리고 길이 4인 직사각형 모양의 파란색 타일의 조합을 이용하여 길이 5인 타일을 만드는 방법은 위 그림과 같이 15 가지가 있다.

이런 식으로 길이 15인 타일을 만드는 방법은 몇 가지일까? 

이 문제를 풀기 위해서는 반드시 116번 문제를 먼저 풀고 와야 한다. 116번 문제에서 사용했던 중복조합에다가 같은 것이 있는 순열을 사용하면 이 문제도 쉽게 해결할 수 있다.

먼저 50개의 타일을 채우기 위해 사용할 파란색, 초록색, 빨간색 타일의 개수를 결정해야 한다. 가능한 모든 경우를 고려해야 하기 때문에 다음과 같이 세 개의 for 문을 사용한다. (파이썬3 를 이용하였다.)

 

for i in range(int(50 / 4) + 1):
    for j in range(int((50 - i * 4) / 3) + 1):
        for k in range(int((50 - (i * 4) - (j * 3) / 2) + 1):

위에서 \(i\) 는 파란색 타일의 개수를 나타낸다. 0개 에서 12개까지 사용할 수 있다. 

\(j\) 는 초록색 타일의 개수를 나타내는데, 파란색 타일이 \(i\) 개 사용되었다면 남는 길이는 \(50 - (i \times 4)\) 이므로 \(j\) 는 0개부터 \(50-(i \times 4)\) 를 3으로 나눈 몫까지 변할 수 있다.

또한 \(k\) 는 빨간색 타일의 개수를 나타내는데, 파란색 타일이 \(i\) 개, 초록색 타일이 \(j\) 개 사용되었다면 남는 길이는 \(50 -(i \times 4) - (j \times 3)\) 이므로 \(k\) 는 0개부터 \(50 - (i \times 4) - (j \times 3)\) 을 2로 나눈 몫까지 변할 수 있다.

이렇게 세 개의 루프 안에서 각 타일의 개수가 결정되었다면 이제 나는 길이만큼 1을 세우고, 그 사이사이와 양끝을 포함한 자리 중 이들이 들어갈 자리를 중복조합으로 선택해 준 다음, 이것들을 같은 것이 있는 순열을 이용하여 나열해 주면 된다. 갑자기 많은 말이 나와서 뭔지 모르겠으면 다음의 예를 보자.

예를 들어, 길이 25인 검은색 타일을 파란색 1개, 초록색 2개, 빨간색 3개를 이용하여 채우는 경우를 생각해보자. 파란색, 초록색, 빨간색 타일에 의하여 채워지는 총 타일의 길이는 \( (1 \times 4) + (2 \times 3) + (3 \times 2) = 16\) 이 된다. 그럼 남는 길이는 14 이므로 일단 14개의 일을 세운다. 

① 1 ② 1 ③ 1 ④ 1 ⑤ 1 ⑥ 1 ⑦ 1 ⑧ 1 ⑨ 1 ⑩ 1 ⑪ 1 ⑫ 1 ⑬ 1 ⑭ 1 ⑮

세 가지 색의 타일을 전부 합쳐 6개를 나열해야 하므로 우리는 ①~⑮ 자리 중에 6군데를 중복조합으로 선택한다. 

만약 ② ② ⑥ ⑩ ⑩ ⑮ 가 선택되었다고 한다면 이 자리들에 파란색 1개, 초록색 2개, 빨간색 3개를 끼워 넣어주면 된다. 그런데 여기에도 나열하는 순서가 있기 때문에 이 6개를 나열하는 경우의 수를 계산해야 한다. 이때 이용하는 것이 같은 것이 있는 순열의 수이다. 총 6개를 나열하는데 같은 것이 2개, 3개 있으므로 나열하는 경우의 수는 \[\dfrac{6!}{2! \times 3!}\] 개가 된다. 결국 25개의 검은색 타일을 파란색 1개, 초록색 2개, 빨간색 3개를 이용하여 채우는 방법은 \[{_{15}}{\rm H}_{6} \times \dfrac{6!}{2! \times 3!} = {_{20}}{\rm C}_6 \times \dfrac{6!}{2! \times 3!}\] 가지가 되는 것이다. 

이런 식으로 새 개의 루프가 도는 동안 경우의 수를 계산하여 다 더해주면 원하는 답을 얻을 수 있다.