프로젝트 오일러 116번

A row of five black square tiles is to have a number of its tiles replaced with colored oblong tiles chosen from red (length two), green (length three), or blue (length four).

If red tiles are chosen there are exactly seven ways this can be done.

If green tiles are chosen there are three ways.

And of blue tiles are chosen there are two ways.

Assuming that colors cannot be mixed there are 7+3+2=12 ways of replacing the black tiles in a row measuring five units in length.

How many different ways can the black tiles in a row measuring fifty units in length be replaced if colors cannot be mixed and at least one colored tile must be used? 

---

길이 1인 정사각형 모양의 검은색 타일 5개로 이루어진 타일의 일부 또는 전부를 길이 2인 직사각형 모양의 빨간색 타일, 길이 3인 직사각형 모양의 초록색 타일, 길이 4인 직사각형 모양의 파란색 타일로 바꾸려고 한다.

만약 빨간색 타일을 이용하여 검은색 타일을 바꾸는 방법은 위 그림처럼 7가지, 초록색 타일을 사용하면 3가지, 파란색 타일을 사용하면 2가지가 있다.

만약 빨간색, 초록색, 파란색 타일을 동시에 사용할 수 없다면 5개의 검은색 타일의 일부 또는 전부를 다른 색으로 바꾸는 방법은 7+3+2=12 가지가 된다.

빨간색, 초록색, 파란색 타일을 동시에 사용하지 않으면서 일렬로 나열된 검은색 타일 50개의 일부 또는 전부를 바꾸는 서로 다른 방법은 몇 가지나 될까? 

이 문제 역시 중복조합을 이용하여 간단하게 해결할 수 있다. 

(중복조합의 개념이 필요하다면 관련 게시물 을 확인하세요)

예를 들어, 길이 2인 빨간색 타일을 한 개만 사용하는 경우를 생각하자.

검은색 타일의 길이가 5이므로, 빨간색 타일 하나를 사용할 경우 남는 검은색 타일의 개수는 3개다.

그렇다면 먼저 1 세 개를 그림과 같이 나열한 다음

①   1   ②   1   ③   1   ④

그 양 끝과 사이사이에 (여기서는 ①, ②, ③, ④ 로 나타내었다.) 2 하나를 끼워 넣는 다고 생각하면 된다. 그렇다면 ①, ②, ③, ④ 중에 하나를 선택하여 그 자리에 2를 끼워 넣으면 되고, 각각이 선택되었을 때의 결과는 다음과 같다.

2111

1211

1121

1112

이제 빨간색 타일 2개를 사용하는 경우를 생각해 보자.

빨간색 타일 2개면 길이가 4가 되고, 검은색 타일은 하나만 남게 된다. 위와 같이 생각하면 

①  1  ②

이 되고, ① 이나 ② 중에 2군데를 선택하여 2 두 개를 끼워 넣으면 된다. 중요한 것은 중복으로 선택할 수 있다는 것이고, 두 군데 모두 동일한 빨간색 타일이 들어갈 것이기 때문에 순서는 고려하지 않는다는 것이다. 즉, 중복조합으로 ①, ② 두 군데 중 2개를 선택하면 된다는 것이다. 이 경우 ①①, ①②, ②② 가 선택되는 것이 가능하고 각각의 경우에 대한 결과는 다음과 같다. 

221

212

122

이렇게 생각하면 쉽게 그 경우의 수를 구할 수 있다. 

50개의 검은색 타일을 빨간색 타일로 채운다고 할 때는 빨간색 타일을 1개부터 25개까지 사용하는 것이 가능하므로 각각에 대해서 위와 같은 방법을 적용하면 된다. 예를 들어, 빨간색 타일을 10개 사용한다고 하면 나머지 길이는 30이므로 1을 30개 나열하고 그것들 사이사이와 양끝까지 포함한 31개 자리 중 중복조합으로 10개의 자리를 선택하여 빨간색 타일을 끼워 넣어주면 원하는 경우의 수를 구할 수 있는 것이다. 경우의 수는 다음과 같다.

\[_{31}{\rm H}_{10} = {_{31+10-1}}{\rm C}_{10} = {_{40}}{\rm C}_{10} = 847660528\]

초록색 타일의 길이는 3이므로 초록색 타일의 경우 1개부터 16개까지 사용이 가능하다. 초록색 타일을 8개 사용한다고 하면 그 길이가 24이므로 26개의 1을 나열한 후, 그 사이사이와 양끝을 포함한 27개의 자리 중 중복조합으로 8개의 자리를 선택하여 초록색 타일을 끼워 넣어주면 된다.

파란색 타일의 경우도 마찬가지로 생각해주면 된다.