알고스팟 원주율 외우기 PI

https://algospot.com/judge/problem/read/PI

algospot.com :: PI

 

 

 

 

<접근방법>

딱 봐도 dp문제인 것을 알 수 있습니다.

길이가 3, 4, 5

방법이 1, 2, 3, 4, 5

인 것을 메모이제이션 하면서 전부 돌아보면 되겠습니다.

구현이 좀 귀찮습니다.

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <limits.h>
using namespace std;

int tc, n;
int a[101][101], cache[101][101], cache2[101][101];
int ret, now_max, now_max_cnt;


//좌표를 받아서 최대 경로의 갯수를 출력
int path(int y, int x) {
	//기저사례
	if (y == n) return 0;

	//중복방문
	int &res = cache[y][x];
	if (res != -1) return res;

	//계산
	res = max(path(y+1, x+1), path(y+1, x)) + a[y][x];

	return res;
}

//(y,x)에서 시작하여 맨 밑줄까지 갔을 때, 최대 경로의 수
int count(int y, int x) {
	//기저사례
	if (y == n-1) return 1;

	//중복방문
	int &res = cache2[y][x];
	if (res != -1) return res;

	//계산
	int a = cache[y+1][x];
	int b = cache[y+1][x+1];

	res = 0;
	if (a == b) {
		res += (count(y + 1, x + 1) + count(y + 1, x));
	}
	else if (a > b) {
		res += count(y + 1, x);
	}
	else {
		res += count(y + 1, x + 1);
	}

	//리턴
	return res;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> tc;
	while (tc--) {
		memset(cache, -1, sizeof(cache));
		memset(cache2, -1, sizeof(cache2));

		cin >> n;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				cin >> a[i][j];
			}
		}

		path(0, 0);
		
		cout << count(0, 0) <<'\n';
	}

	return 0;
}

 

 

---

 

 

<느낀 점>

 

 

 

 

 

 

 

[참고]

-프로그래밍 대회에서 배우는 알고리즘 문제해결전략1