[백준] 15735번 삼각 c++

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

15735번: 삼각

문제

N층의 정삼각형이 주어졌을때, 크고 작은 정삼각형의 개수가 몇개인지 알아보자.

N이 2일 경우 정답은 5이다.

입력

첫 번째 줄에 정삼각형 탑의 층 N이 주어진다. (1 ≤ N ≤ 10,000)

출력

첫 번째 줄에 크고 작은 삼각형의 개수의 합을 출력한다.

 

 

 

접근방식

삼각형 탑 높이 n에 따라서 삼각형 개수가 어떻게 달라지는지 규칙을 찾아내어 코드로 구현하였다.

처음에는 1개짜리 삼각형과 똑바로 서있는(?) 삼각형의 규칙만 찾아서 구현을 했다. 역으로 뒤집어진 삼각형이 포함된다는 것을 코딩후에 알아 생각을 다시 해야 했다.

규칙을 찾아서 구간합 배열을 만들었다. 그리고 배열을 활용하여  결과값을 계산하는 방식으로 구현하였다.

#include <iostream>

using namespace std;

int main(){
  long long num_one[10001]={0,};
  long long num_others[10001]={0,};
  long long result=0;
  int n; cin >> n;

  num_one[1]=1;
  for(int i=1; i<10001; i++){
    num_others[i] = num_others[i-1] + i;
    if(i!=1) num_one[i] = num_one[i-1]+2;
  }
  for(int i=1; i<n; i++){
    result+=num_others[i]+num_one[i];
  }
  result+=num_one[n];

  long long sum[10001]={0,}; // 역삼각형 개수 계산을 위한 구간합배열
  sum[0]=0; sum[1]=1;
  for(int i=1; i<10001; i++)
    sum[i]=sum[i-1]+i;
  for(int i=n-3; i>0; i=i-2){
    result+=sum[i];
  }
  printf("%lld\n", result);
  return 0;
}

 

느낀 점

생각을 완전히 끝냈다고 생각했음에도 역삼각형 형태의 정삼각형들을 고려하지 못했다. 생각이 1차적으로 끝나도 더 예외가 없는지 꼼꼼히 생각하는 버릇을 들여야 겠다.