문제
https://www.acmicpc.net/problem/16395
문제해설
n과 k가 주어지고
파스칼의 삼각형에서
n번째 줄의 k번째 수를 구하면 된다.
문제풀이
2차원 dp로 풀면 쉽고 간단하게 풀 수 있지만
1차원만 생각하는 바람에 어렵게 짰다.
물론 공간복잡도 상으로는 1차원이 더 효율적이다.
1차원으로 짠다면 (i * (i - 1)) / 2 + 1에서부터
(i * (i + 1)) / 2까지가 i번째 줄이다.
이것을 참고하면 풀 수 있을 것이다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<algorithm>
using namespace std;
int dp[500];
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, k; cin >> n >> k;
dp[1] = dp[2] = dp[3] = 1;
for (int i = 3; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (j == 1 || j == i)
dp[(i * (i - 1)) / 2 + j] = 1;
else
dp[(i * (i - 1)) / 2 + j] =
dp[((i - 2) * (i - 1)) / 2 + j - 1] + dp[((i - 2) * (i - 1)) / 2 + j];
}
}
cout << dp[(n * (n - 1)) / 2 + k];
return 0;
}