15489 파스칼 삼각형

파스칼 삼각형에서

시작점과 변의 길이가 주어졌을때

그 안에 속하는 삼각형 내부의 숫자들의 합을 구하는 문제

1. 문제

---

간단 설명

파스칼 삼각형이란?

간단히 말하자면, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다.

1. 첫 번째 줄에는 1을 쓴다.
2. 그 다음 줄을 만들 때 바로 위의 왼쪽 숫자와 오른쪽 숫자를 더한다
   • 예를 들어, 네 번째 줄의 숫자 1과 3을 더하여 다섯 번째 줄의 4가 만들어진다.

t[0] = {1}
t[1] = {1, 1}
t[2] = {1, 2, 1} 
...
t[N] = {1, t[N-1][0] + t[N-1][1], t[N-1][1] + t[N-1][2], ... , t[N-1][N-2] + t[N-1][N-1], 1}

으로 정의된다

즉 t[i][j] 원소는 t[i][j] = t[i-1][j-1] + t[i-1][j]로 표현할 수 있다

2. 문제 분석

---

필요변수

시작 좌표 R, C, 변의 길이 W

(단, 2 ≤ R+W ≤ 30, 2 ≤ C+W ≤ 30, 1 ≤ W ≤ 29, C ≤ R) 이므로

W가 1일때, R은 최대 29

삼각형의 최대 크기는 30이므로

파스칼 삼각형을 저장할 2차원 배열 t[31][31]

값들의 합을 저장할 sum

주의점

• 배열의 인덱스 참조에 주의할 것

알고리즘

1. 필요 변수 입력 받고, 파스칼 삼각형 통째로 만들기
2. [R][C] 에서 변이 W인 삼각형의 합 구하기

시간 복잡도는 2중 for문밖에 없으므로 O(N^2)

최악의 경우는 항상 파스칼 삼각형을 통째로 구하는 경우로 고정됨

N이 커봤자 30정도 이므로 900번씩 두번 수행한다(파스칼 삼각형 초기화할때, 더할때)

3. 소스코드

---

#include <iostream>

using namespace std;

int main() {
	int R, C, W;
	cin >> R >> C >> W;

	int t[35][35] = { 0 }; // 넉넉히 만듬 최대 30임

	// 1. 30줄까지 파스칼 삼각형 만들기
	t[0][0] = 1;
	t[1][0] = 1;
	t[1][1] = 1;

	for (int i = 2; i < 30; i++) {
		for (int j = 0; j < i + 1; j++) {
			if (j == 0 || j == i)
				t[i][j] = 1;
			else
				t[i][j] = t[i - 1][j - 1] + t[i - 1][j];
		}
	}
	
	// 2. 첫째 줄에 R번째 줄, C번째 수를 위 꼭짓점으로 하는 
	// 한 변이 포함하는 수의 개수가 W인 정삼각형과 그 내부에 있는 수들의 합을 출력 
	int sum = 0;
	
	int idx = 0;
	for (int i = R - 1; i < R - 1 + W; i++) { // R번째 줄
		for (int j = C - 1; j <= C - 1 + idx; j++) { // C번째 수 

			sum += t[i][j];
		}
		idx++;
	}
	cout << sum;

	return 0;
}

맨날 시간복잡도에 털렸으므로

간단한 문제라도 시간복잡도를 구하는 연습을 해야겠다