문제접근
•
구하려는 위치가 메모이제이션이 되어 있으면 그대로 사용하고 메모이제이션이 되어있지 않으면 규칙에 맞게 재귀를 통해서 값을 구함
놓쳤던 부분
•
메모이제이션을 안 하고 각 위치를 계산할때마다 재귀가 돌아서 시간 초과
•
크기가 크지 않기 때문에 미리 값을 다 구해놓는 방법. 결국 같은 코드인데 내가 더 비효율적으로 풀었음
#include <iostream>
#include <algorithm>
using namespace std;
int dp[31][31];
int r, c, w, ans;
int main() {
cin >> r >> c >> w;
dp[1][1] = 1;
for (int i = 1; i <= 30; i++) {
for (int j = 1; j <= i; j++) {
if (j == 1 || j == i) dp[i][j] = 1;
else dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}
}
for (int i = 0; i < w; i++) {
for (int j = 0; j <= i; j++) {
ans += dp[r + i][c + j];
}
}
cout << ans;
}
C
복사
코드
2024 KB
0 ms
#include <iostream>
#include <cstring>
using namespace std;
int dp[31][31];
int r, c, w;
int pascal(int row, int col) {
if (dp[row][col] != 0)
return (dp[row][col]);
if (col == 1 || col == row) {
dp[row][col] = 1;
return (dp[row][col]);
}
return (dp[row][col] = pascal(row - 1, col - 1) + pascal(row - 1, col));
}
int main(void) {
long long answer = 0;
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> r >> c >> w;
memset(dp, 0, sizeof(dp));
for (int i = r; i < r + w; i++)
for (int j = c; j <= c + i - r; j++) {
if (dp[i][j] == 0)
pascal(i, j);
answer += dp[i][j];
}
cout << answer;
return (0);
}
C++
복사
