글 읽기 - 바텀업으로 풀었다가 탑다운으로 한번 풀어보았습니다.

gksrlfw 4년 전 0

1 2 3 4 5

6 7 8 9 0

이렇게 있으면 대각선과 대각선 한칸 뒤의 숫자를 비교해서 큰 수를 리턴하는 식으로 점화식을 세웠습니다.

(1번과 7,8번 비교, 7번과 3,4번 비교 이런식으로)

바텀업으로 했을 땐 바로 정답이 나오는데 탑다운으로 하니까 잘 안나오네요... 어디를 수정해야될까요?

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int d[2][100001];
int p[2][100001];
// 탑다운
int go(int c, int n) {
	int sum = 0;    

	if (n < 1) return 0;
	if (d[c][n] > 0) return d[c][n];
	d[c][n] += max(go(1 - c, n - 1), go(1 - c, n - 2)) + p[c][n];
	d[1 - c][n] += max(go(c, n - 1), go(c, n - 2)) + p[1 - c][n];
	sum = max(d[c][n], d[1 - c][n]);
	cout << sum << " ";
	return sum;
}
int main() {
	int t;
	cin >> t;

	while (t--) {
		memset(d, 0, sizeof(d));
		int n;
		cin >> n;
		for (int i = 0; i < 2; i++) {
			for (int j = 1; j <= n; j++) {
				cin >> p[i][j];
			}
		}
        /*    바텀업
		d[1][1] = p[1][1];
		d[0][1] = p[0][1];
		for (int i = 2; i <= n; i++) {
			d[0][i] = max(d[1][i - 1], d[1][i - 2]) + p[0][i];
			d[1][i] = max(d[0][i - 1], d[0][i - 2]) + p[1][i];
		}
		cout << max(d[0][n],d[1][n]) << endl;
        */
        cout<<go(0,n)<<endl;
	}
}

skysign 3년 전 0

대각선이나, 탑다운, 바텀이 문제인건 아니구요,

사용하지 않는 컬럼이 있을 수도 있다. 이 부분을 고려해서, 코딩해야 합니다.

문제풀이는 아래영상 참고하세요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

바텀업으로 풀었다가 탑다운으로 한번 풀어보았습니다.

gksrlfw 4년 전 0

skysign 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말