백준 3049번 다각형의 대각선 C++

리뷰

노가다를 통해 점화식을 세우고 오랜시간이 걸려 풀었다..

 

문제 풀이

1. 101길이의 정수형 벡터를 0으로 초기화 한다.
2. n 값을 입력 받고 정수형 변수 plus1과 plus2를 각각 1로 초기화 한다.
3. 3번 인덱스의 경우 0이 확정이므로 4부터 for문을 돌려준다.
4. 현재 값은 이전 인덱스 값에 plus2를 더해준 값이다.
5. plus1에 현재 for문의 i에서 2를 뺀 만큼 더해준다.
6. plus2에 plus1 만큼 더해준다.
7. dp의 n번째 인덱스를 출력해 준다.

 

참고 사항

n	3	4	5	6	7	8	9	10
dp[n]	0	1	5	15	35	70	126	210
plus1	0	1	4	10	20	35	56	84
plus2	0	1	3	6	10	15	21	28

엄청난 노가다로 위의 식을 도출해 냈다.

문제를 풀고 나서 chatGPT에게 물어보니 식이 존재했다. 대각선이 교차하는 점의 수는 nC4였다.

 

정답 코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
	vector<int> dp(101, 0);
	int n, plus1 = 1, plus2 = 1;
	cin >> n;
	for (int i = 4; i <= 100; i++) {
		dp[i] = dp[i - 1] + plus2;
		plus1 += i - 2;
		plus2 += plus1;
	}
	cout << dp[n];
}