[BAEKJOON] 백준 15236: Dominos (C#)

문제 링크

https://www.acmicpc.net/problem/15236

 

 

문제

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.

 

 

입력

The first and only line of input contains a single integer, N (1 ≤ N ≤ 1000), the size of the complete set.

 

 

출력

The first and only line of output should contain a single integer, total number of spots in a complete size N set.

 

 

 

통과한 답안

namespace _15236
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            double answer = 0;

            for (int i = 0; i <= n; i++)
            {
                answer += i * (n + 1 - i);
            }

            for (int i = n; i > 0; i--)
            {
                answer += i * (i + 1);
            }

            Console.WriteLine(answer);
        }
    }
}

 

두 개의 면으로 나눠진 도미노에 각각의 면에 최대 n개의 점을 찍을 수 있을 때,

n에 대한 모든 점의 합을 구하는 문제이다.

 

예시에 나온 것처럼 n이 2인 경우,

 

0  0  1  0  1  2

0  1  1  2  2  2

 

의 조합을 만들 수 있으며, 이 경우에 모든 점의 합은 12개이다.

 

이를 간단하게 생각하면 위의 점이 0개, 1개, 2개인 세 그룹으로 나눌 수 있고,

위의 점이 0개인 경우의 아래 점은 0, 1, 2(0부터 n까지)

위의 점이 1개인 경우의 아래 점은 1, 2(1부터 n까지)

위의 점이 2개인 경우의 아래 점은 2(2부터 n까지)

로 계산할 수 있다.

 

즉, 위의 점과 아래의 점을 분리하여 생각하고 최대 n개의 점을 찍을 수 있다고 한다면

위의 점이 0개인 경우는 (n+1)개이며, 이 경우의 아래점은 0부터 n까지이고

위의 점이 1개인 경우는 n개이며, 이 경우의 아래점은 1부터 n까지이고

위의 점이 2개인 경우는 (n-1)개이며, 이 경우의 아래점은 2부터 n까지이다

 

따라서 이 둘을 분리하여 코드로 나타낸 것이 아래와 같은데,

// 위의 점의 총 개수
for (int i = 0; i <= n; i++)
{
    answer += i * (n + 1 - i);
}

 

위의 점의 개수는 0 * (n + 1) + 1 * n + 2 * (n - 1) + ... + (n - 1) * 2 + n * 1로 구할 수 있다.

이 그림에서 윗줄의 점은 0이 3개, 1이 2개, 2가 1개 있다.

 

// 아래점의 총 개수
for (int i = n; i > 0; i--)
{
    answer += i * (i + 1);
}

 

아래점의 개수는 위의 최대 n개의 점을 찍는 경우에서

위의 점이 0개일 때 0부터 n까지,

위의 점이 1개일 때 1부터 n까지,

위의 점이 2개일 때 2부터 n까지,

위의 점이 n개일 때 n부터 n까지이므로

n이 (n + 1)개, (n - 1)이 n개, (n - 2)가 (n - 1)개... 1이 2개, 0이 1개 있으므로

위의 식처럼 n * (n + 1) + (n - 1) * n + (n - 2) * (n - 1) + ... + 1 * 2 + 0 * 1로 구할 수 있다.

이 그림에서 아랫 줄의 점은 0이 1개, 1이 2개, 2가 3개 있다.

 

 

코드만 본다면 조금은 복잡해보일 수 있지만,

위와 아래의 두 면의 점의 개수를 각각 분리하여 계산한 방식으로

시간 복잡도가 O(2N)으로 총 점의 개수를 구할 수 있는 점이 장점인 코드이다.