백준/실버
[백준 15489번] 파스칼 삼각형 (C++)
게임개발기원
2023. 12. 4. 18:07
문제링크 : https://www.acmicpc.net/problem/15489
15489번: 파스칼 삼각형
첫째 줄에 양의 정수 R, C, W가 공백을 한 칸씩 두고 차례로 주어진다. (단, 2 ≤ R+W ≤ 30, 2 ≤ C+W ≤ 30, 1 ≤ W ≤ 29, C ≤ R)
www.acmicpc.net
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;
int R, C, W, result;
int dp[31][31];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> R >> C >> W;
for(int i=1; i<=30; i++)
{
for(int j=1; j<=30; j++)
{
if(j==1 || j==i) dp[i][j]=1; //끝 모서리부분은 1고정
else dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
}
}
for(int i=R; i<R+W; i++)
{
for(int j=C; j<=C+i-R; j++)
{
result += dp[i][j]; //범위내 더해주기
}
}
cout << result;
return 0;
}
상당히 유명한 파스칼의 삼각형 문제를 이용한 dp 문제이다.
처음에 파스칼의 삼각형을 먼저 채워주고 시작한다.
그 이후에 문제에 주어진 범위내의 값만 따로 더해주고 출력해주면 된다.