문제접근🤔

구하려는 위치가 메모이제이션이 되어 있으면 그대로 사용하고 메모이제이션이 되어있지 않으면 규칙에 맞게 재귀를 통해서 값을 구함

놓쳤던 부분😅

메모이제이션을 안 하고 각 위치를 계산할때마다 재귀가 돌아서 시간 초과

크기가 크지 않기 때문에 미리 값을 다 구해놓는 방법. 결국 같은 코드인데 내가 더 비효율적으로 풀었음

#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;
}

코드😁

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);
}