TRIANGLEPATH 시간초과 관련 질문있습니다 yhb0730 아래 코드의 함수중 sum2()는 제가 작성한 코드, sum()는 책에서 나오는 답안입니다. 제 생각으로는 sum2와 sum이 재귀호출되는 갯수는 같다고 생각해서 sum2로 제출을 했는데 시간초과가 떴습니다. sum()은 시간내에 통과를 했고요. 둘다 비슷한 시간이 걸릴거라고 생각했는데 시간이 이렇게나 차이가 나는 이유를 모르겠습니다. 제가 뭔가 잘못 생각한게 있는지 알고 싶습니다 #include<iostream> #include<cstring> #include<algorithm> using namespace std; int cache[101][101]; int triangle[101][101]; int n; int maxNum; void init(); void sum2(int y, int x); int sum(int y, int x); int main(void) { int testcase; cin >> testcase; while (testcase--) { init(); cout << sum(0, 0) << endl; //sum2(0, 0); //cout << maxNum << endl; } return 0; } void init() { int i,j; maxNum = 0; memset(cache, 0, sizeof(cache)); cin >> n; for (i = 0; i < n; ++i) { for (j = 0; j <= i; ++j) { cin >> triangle[i][j]; } } //cache[0][0] = triangle[0][0]; } int sum(int y, int x) { if (y == n - 1) return triangle[y][x]; int& ret = cache[y][x]; if (ret != 0) return ret; return ret = max(sum(y + 1, x), sum(y + 1, x + 1)) + triangle[y][x]; } void sum2(int y, int x) { if(y == n-1) { maxNum = max(maxNum, cache[y][x]); return; } if (cache[y + 1][x] < cache[y][x] + triangle[y + 1][x]) { cache[y + 1][x] = cache[y][x] + triangle[y+1][x]; } cache[y + 1][x + 1] = cache[y][x] + triangle[y+1][x+1]; sum2(y + 1, x); sum2(y + 1, x + 1); } 7년 전
1개의 댓글이 있습니다. seico75 자세한 로직은 모르겠지만... 시간만 본다면 메모이제이션의 유무 차이로 보입니다. sum 은 if (ret != 0) return ret; /// 이미 계산을 했다면,, 부분에서 재귀를 안탈 수 있습니다. 하지만 sum2 는 무조건 2번 재귀를 호출하는 구조입니다. 7년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
yhb0730
아래 코드의 함수중 sum2()는 제가 작성한 코드, sum()는 책에서 나오는 답안입니다. 제 생각으로는 sum2와 sum이 재귀호출되는 갯수는 같다고 생각해서 sum2로 제출을 했는데 시간초과가 떴습니다. sum()은 시간내에 통과를 했고요. 둘다 비슷한 시간이 걸릴거라고 생각했는데 시간이 이렇게나 차이가 나는 이유를 모르겠습니다. 제가 뭔가 잘못 생각한게 있는지 알고 싶습니다
7년 전