[백준 02921] 도미노 [Java]

문제

도미노는 여러 종류의 타일 게임에서 사용하는 조각이다. 도미노 조각은 두 칸으로 이루어져 있다. 각 칸에는 점이 찍혀있는데, 점이 안 찍혀져 있을 수도 있다. 점의 개수는 세트의 크기에 의해서 결정된다. 세트의 크기가 N인 도미노 세트에서 점의 개수는 0보다 크거나 같고, N보다 작거나 같다. 두 도미노에 찍혀잇는 점의 개수가 같다면, 두 도미노는 동일한 것이다. 예를 들어, 점이 2개와 8개 찍혀있는 도미노는 8개와 2개 찍혀있는 도미노와 같은 도미노이다.

크기가 N인 도미노 세트는 N 또는 그보다 작거나 같은 점을 포함하는 가능한 도미노를 모두 포함하고 있고, 각 도미노는 중복되지 않는다. 다음은 크기가 2인 도미노 세트이다.

N을 입력받은 뒤, 크기가 N인 도미노 세트에는 점이 몇 개 찍혀 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도미노 세트의 크기 N (1 ≤ N ≤ 1000)이 주어진다.

출력

크기가 N인 도미노 세트에 찍혀 있는 점의 개수를 출력한다.

---

풀이

도미노는 두 칸으로 이루어져 있는데, 두 도미노에 찍힌 점의 개수(조합)가 동일하면 하나의 도미노로 취급한다.

때문에, 도미노는 ( 0, 0 ) ~ (N, N)에 대해 중복을 피하기 위해 ( i, i ), ( 0, i + 1 ), ( 1, i + 1 ), ..., ( i + 1, i + 1), ( 0, i + 2)와 같은 패턴으로 점이 찍힌다. 아래의 코드를 참고하자.

int sum = 0;
for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= i; ++j) {
    	sum += i + j;
    }
}

 

문제에서 주어진대로 2중 loop를 돌며 도미노 세트에 찍힌 점의 개수를 구해도 되지만, 규칙이 존재한다.

i에 대해 j는 1 ~ i의 등차수열을 만족하고, ( ( i * ( i + 1) ) / 2 )

n에 대해 i는 n * (n + 1)을 만족한다.

 

입력값 N에 대해 아래의 f(N)에 대한 등차수열이 성립한다.

 

등차수열 N ( N + 1 ) 에 대해 계산 과정을 줄여보았다. 

다음과 같이 상수항 시간 내 계산 가능한 항등식을 구할 수 있다.

 

결국 입력값 N에 대한 점의 개수에 대해 아래의 공식이 성립한다.

 

계산 결과에 대해 casting 해준 후 출력해주자.

---

소스코드

보기

---

출처

2921번: 도미노