알고스팟 Domino (DOMINO) 문제 파이썬으로 풀기

도미노에 있는 마크의 수를 세는 문제이다.

처음 문제를 보면 갯수를 어떻게 세야 할지 걱정이 앞설 수 있지만, 아주 간편한 방법이 있다.

 

예제에 있는 입력과 출력을 표로 한번 나타내보자.

입력	출력
2	12
3	30
15	2040

입력이 2가 들어왔을때, 출력은 12이다. 그리고 문제 설명에서 도미노가 2칸일때 6개의 경우가 나온다는 것을 보여주었다. 여기서 출력이 입력과 경우의 수의 곱인가? 하고 추측해볼 수 있다.

입력이 3일때 출력은 30이다. 앞서 했던 추측이 맞다면, 30은 3과 10의 곱이므로 도미노칸이 3일경우 10개의 경우가 나올 것이다.

그리고 입력이 1이 들어왔을때를 가정해보자. 도미노 1칸에는 마크가 0개, 1개, 2개일 경우가 있으므로, 경우의 수는 3개이다.

 

그럼 여기까지 진행한 것을 바탕으로 위의 표를 고쳐보겠다.

입력	출력	출력=입력*경우의수?
1	3	3=1*3
2	12	12=2*6
3	30	30=3*10
15	2040	2040=15*136

여기서 주목해 볼 부분이 있다. 출력이 입력과 경우의 수의 곱이라는 추측이 맞을 경우에서의 경우의 수를 보자.

입력이 1일때 경우의 수는 3이다. 입력이 2일때는 경우의 수는 6이다. 입력이 3일때 경우의 수는 10이다.

3 6 10이라. 어디서 본 거 같은 수열이다.

3=1+2, 6=1+2+3, 10=1+2+3+4이다. 즉, 1부터 n까지의 자연수의 합이다.

 

이점을 유념하고, 입력과 경우의 수를 봐보자.

입력	경우의 수	자연수의 합으로 나타내기
1	3	1+2
2	6	1+2+3
3	10	1+2+3+4

입력이 n이었을때 경우의 수는 1부터 n+1까지의 합이 된다.

즉, n이 입력일때 경우의 수는 (n+1)*(n+2)/2가 된다.

 

지금까지의 내용을 정리해보면, 입력이 n이었을때 출력은 입력*경우의 수가 되므로, n*((n+1)*(n+2)/2)이 된다.

예를 들어보자면, 입력이 15일때 경우의 수는 16*17/2=136이 된다. 136*15=2040이 되고, 앞서 했던 추측이 맞다고 볼 수 있다.

 

코드를 짜보자.

#domino
 
num=int(input())  # 입력
tilenum=(num+1)*(num+2)/2  # 경우의 수
result=num*tilenum  # 출력
print(int(result))  # int를 안해주면 소수점이 붙어 나온다

매우 간단하다.

 

느낀점:

1. 처음 할땐 어려워보였는데, 막상 수학으로 풀어보니 매우 간단한 문제였다.