[백준/파이썬] 15236번 Dominos 풀이
업데이트:
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 15236번 Dominos
- 문제풀이 코드 GitHub 링크
- 제출 언어: Python 3
- 원문 출처: Olympiad > All-Ireland Programming Olympiad > 2017 AIPO Preliminary Round 5 번
풀이
문제
원문
Dominoes are gaming pieces used in numerous tile games. Each domino piece contains two marks. Each mark consists of a number of spots (possibly zero). The number of spots depends on the set size. Each mark in a size N domino set can contain between 0 and N spots, inclusive. Two tiles are considered identical if their marks have the same number of spots, regardless of reading order. For example tile with 2 and 8 spot marks is identical to the tile having 8 and 2 spot marks. A proper domino set contains no duplicate tiles. A complete set of size N contains all possible tiles with N or less spots and no duplicate tiles. For example, the complete set of size 2 contains 6 tiles:
Write a program that will determine the total number of spots on all tiles of a complete size N set.
번역
N 세트가 하나의 도미노 피스의 각 두 타일에 찍힌 점이 모두 N개인 도미노 까지의 세트를 뜻합니다.
위 그림은 2세트 인 셈이죠.
N이 주어질 때, 해당 세트의 모든 점 수를 구하면 됩니다. 위 그림은 2세트에 점은 총 12개 있습니다.
- 자세한 문제 및 입출력 예제는 상단의 문제 출처(백준 홈페이지)를 참조해주세요
코드
n=int(input())
print(n*(n+1)*(n+2)//2)
설명
우선, n을 입력받습니다. n이 충분히 작으므로(1000 이하) 단순 반복으로도 풀 수 있습니다만, 규칙을 찾아봅시다.
위쪽 타일에 집중해보면, n세트의 마지막 도미노 피스까지 각 세트당 점이 0, 0~1, 0~2, …, 0~n 개로 나타남을 알 수 있습니다.
즉, 1은 n번, 2는 n - 1번, …, n은 1번이 나옵니다. k눈은 n-k+1번이 나오게 되겠죠. 즉, 모든 k눈의 합은 nk-k^2+k가 됩니다.
이번엔 아래쪽 타일을 봅시다. n이 몇이든 상관없이, 아래쪽 타일의 k눈은 k+1번 나올 것입니다. 즉, 모든 k눈의 합은 k^2 + k 이 됩니다.
이제 위의 식과 더해주도록 합시다.
위타일과 아래타일을 통틀어서, k눈의 합은 nk - k^2 + k + k^2 + k = nk + 2k = k(n + 2)가 됩니다. 자연스레, k = 1 ~ n까지의 합은 n(n + 1)(n + 2)/2가 됩니다.
이 수는 당연히 짝수일 것이므로, 정수로 바로 출력하기 위해 /를 //로만 바꾼 수식을 출력해주면 됩니다.
댓글남기기