글 읽기 - 1932번 시간초과

lhb8282 6년 전 0

1932번 시간초과 나는데 어느부분을 고쳐야 할까요??

#include <iostream>
#include <vector>
using namespace std;

int n;
int max_sum;
int triangle[501][501];

void solve(int n, int x, int y, int sum){
	
	if(x > n+1 || y < 0 || y > n+1 || x < 0) {
		if(max_sum < sum){
			max_sum = sum;
		}
		return;
	}

	//왼쪽
	solve(n - 1, x + 1, y, sum + triangle[x+1][y]);
	
	
	//오른쪽
	solve(n - 1, x + 1, y + 1, sum + triangle[x+1][y+1]);
	
}

int main(){
		cin >> n;

		for(int i=0; i<n; i++){
			for(int j=0; j<i+1; j++){
				cin >> triangle[i][j];
			}
		}
		max_sum = 0;
		solve(n + 1 , 0, 0, triangle[0][0]);
		cout << max_sum << endl;
	
}

chogahui05 6년 전 0

메모이제이션은 안 하셨나요?

djm03178 6년 전 0

메모이제이션을 하더라도 지금처럼 앞으로 더해나가는 DFS식으로 풀면 어려울 거 같네요. 하나를 바꾸는 순간 뒷부분까지 모조리 다시 바꿔야 할 수 있으니까요. 형식을 조금 바꾸어서 끝으로부터 반환된 값들을 더해서 저장해둔다면 될지도 모르겠네요.

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

문제

문제

출처

ICPC

1932번 시간초과

lhb8282 6년 전 0

chogahui05 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말