취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15735번 문제인 삼각이다.
문제는 아래 링크를 확인하자.

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

이 글에서 "정삼각형"은 위로 뾰족한 정방향 삼각형이라는 의미로 사용되었다.

위로 뾰족한 정삼각형과 아래로 뾰족한 역삼각형의 개수를 따로 세면 문제를 쉽게 해결할 수 있다.

한 변의 길이가 i인 정삼각형은 (1~(N-i+1)의 총합)개 존재하는 것을 알 수 있다.

한편, 한 변의 길이가 i인 역삼각형은 (1~(N-2i+1)의 총합)개 존재하는 것을 알 수 있다.

위의 각 가짓수를 반복문을 이용하여 전부 더해 문제를 해결하자.

여담으로 이 문제의 답을 나타내는 닫힌 식 또한 알려져있는데, 바로 floor(n(n+2)(2n+1)/8)이다. 이 식으로도 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll arr[10001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 1; i < 10001; i++) {
		arr[i] = arr[i - 1] + i;
	}

	int N; cin >> N;
	ll ans = 0;
	for (int i = 1; i <= N; i++) ans += arr[i];
	for (int i = N - 1; i > 0; i-=2) ans += arr[i];

	cout << ans;
}