BOJ 2921 - 도미노

문제

0부터 N까지의 수가 적힌 도미노 세트가 있다. 모든 도미노에 적힌 점의 합을 구하라. 도미노 (i, j)에서 i <= j이다.

입력

N이 주어진다.

출력

모든 도미노의 점 합을 출력한다.

예제

입력	출력
`2`	`12`

풀이

모든 가능한 도미노 (i, j) 조합을 생성하여 점의 합을 구한다.

i를 0부터 N까지 순회한다
각 i에 대해 j를 0부터 i까지 순회한다 (i >= j 조건)
각 도미노의 점 합 (i + j)를 누적한다
최종 합을 출력한다

핵심 아이디어: 도미노 (i, j)는 i >= j인 모든 조합이므로 이중 반복문으로 O(N^2)에 전체 합을 구한다.

코드

#include <iostream>
using namespace std;
 
int main()
{
  int n;
  int sum = 0;
  cin >> n;
 
  for (int i = 0; i < n + 1; i++)
  {
    for (int j = 0; j < i + 1; j++)
    {
      sum += i + j;
    }
  }
  cout << sum;
 
  return 0;
}

복잡도

시간: O(N^2)
공간: O(1)

문제