[백준 C++] 15489 파스칼 삼각형
문제
파스칼 삼각형은 아래와 같은 모양으로 이루어져 있다. 양 끝을 제외한 각 수는 자신의 바로 왼쪽 위의 수와 바로 오른쪽 위의 수의 합으로 되어있다.
이때 R번째 줄, C번째 수를 위 꼭짓점으로 하는 한 변이 포함하는 수의 개수가 W인 정삼각형과 그 내부를 생각하자. 정삼각형의 변과 그 내부에 있는 수들의 합을 구하고 싶다. 예를 들면, 3번 째 줄, 1번 째 수를 꼭짓점으로 하고 한 변이 포함하는 수의 개수가 4인 정삼각형과 그 내부에 있는 수의 합은 1+(1+3)+(1+4+6)+(1+5+10+10) = 42 이다.
주어진 R, C, W에 대해서 그에 해당하는 합을 구하는 프로그램을 작성하여라.
입력
첫째 줄에 양의 정수 R, C, W가 공백을 한 칸씩 두고 차례로 주어진다. (단, 2 ≤ R+W ≤ 30, 2 ≤ C+W ≤ 30, 1 ≤ W ≤ 29, C ≤ R)
출력
첫째 줄에 R번째 줄, C번째 수를 위 꼭짓점으로 하는 한 변이 포함하는 수의 개수가 W인 정삼각형과 그 내부에 있는 수들의 합을 출력한다.
https://www.acmicpc.net/problem/15489
풀이
2차원배열을 입력받은 R+W값에따라 동적으로 생성후
다시 2중for문으로 해당범위값을 모두 더하여 출력하였다.
딱히 설명할게 없는문제이다.
인덱스 실수만 조심하면될듯..
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
int main(void) {
int R, C, W, **pt;
scanf("%d%d%d", &R, &C, &W);
int size = (R + W);
pt = new int*[size * (size + 1) / 2 + 1];
//pt[i][j] i번째줄 j번째숫자 (1부터시작)
for (int i = 1; i <= size; i++) {
pt[i] = new int[i+1]; //시작인덱스를 1부터셈
pt[i][0] = 0;
}
for (int i = 1; i <= size; i++) { //i번째줄
for (int j = 1; j <= i; j++) { //j번째 숫자
if (j == 1 || j == i) {
pt[i][j] = 1; //양끝숫자는 1
//printf("%d ", pt[i][j]);
}
else {
//왼쪽위 오른쪽위숫자합
pt[i][j] = pt[i - 1][j - 1] + pt[i - 1][j];
//printf("%d ", pt[i][j]);
}
}
//printf("\n");
}
int res = 0;
for (int i = 1; i <= W; i++) {
for (int j = 1; j <= i; j++) {
res += pt[R + i-1][C + j -1];
//printf("%d ", pt[i+ C + R -2][j+ C -1]);
}
//printf("\n");
}
printf("%d", res);
return 0;
}
Author And Source
이 문제에 관하여([백준 C++] 15489 파스칼 삼각형), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cldhfleks2/백준-C-15489-파스칼-삼각형저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)