rogramers : 땅따먹기 - C++
21212 단어 level2DPPROGRAMERSDP
땅따먹기
코드
[ 백트래킹 코드 ] - 시간초과
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int ans,N;
vector<int> arr;
vector<vector<int>> val;
void func(int depth, int start, int prev)
{
int tot=0;
if(depth == N){
for(int i=0;i<N;i++)
tot += arr[i];
ans=max(ans,tot);
}else{
for(int i=start;i<N;i++)
{
for(int j=0;j<4;j++)
{
if(prev == j) continue;
arr[depth] = val[i][j];
func(depth+1, i+1, j);
}
}
}
}
int solution(vector<vector<int>> land)
{
int answer = 0;
N = land.size();
arr.resize(N);
val.resize(N);
for(int i=0;i<N;i++)
for(int j=0;j<4;j++)
val[i].push_back(land[i][j]);
func(0, 0, -1);
answer = ans;
return answer;
}
- 문제
: N이 너무 커서 시간초과
[ 정답 풀이 ] - DP
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int d[100003][4];
int solution(vector<vector<int>> land)
{
int answer = 0;int N = land.size();
d[0][0] = land[0][0];d[0][1] = land[0][1];
d[0][2] = land[0][2];d[0][3] = land[0][3];
for(int i=1;i<N;i++)
{
d[i][0] = max(d[i-1][1], max(d[i-1][2], d[i-1][3])) + land[i][0];
d[i][1] = max(d[i-1][0], max(d[i-1][2], d[i-1][3])) + land[i][1];
d[i][2] = max(d[i-1][0], max(d[i-1][1], d[i-1][3])) + land[i][2];
d[i][3] = max(d[i-1][0], max(d[i-1][1], d[i-1][2])) + land[i][3];
}
answer = max(d[N-1][0], max(d[N-1][1], max(d[N-1][2], d[N-1][3])));
return answer;
}
- key point!
: DP의 핵심인 메모제이션(memoization)
을 사용해야 한다
Author And Source
이 문제에 관하여(rogramers : 땅따먹기 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/Programers-땅따먹기-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
[ 백트래킹 코드 ] - 시간초과
#include <iostream> #include <vector> #include <algorithm> using namespace std; int ans,N; vector<int> arr; vector<vector<int>> val; void func(int depth, int start, int prev) { int tot=0; if(depth == N){ for(int i=0;i<N;i++) tot += arr[i]; ans=max(ans,tot); }else{ for(int i=start;i<N;i++) { for(int j=0;j<4;j++) { if(prev == j) continue; arr[depth] = val[i][j]; func(depth+1, i+1, j); } } } } int solution(vector<vector<int>> land) { int answer = 0; N = land.size(); arr.resize(N); val.resize(N); for(int i=0;i<N;i++) for(int j=0;j<4;j++) val[i].push_back(land[i][j]); func(0, 0, -1); answer = ans; return answer; }
- 문제
: N이 너무 커서 시간초과
[ 정답 풀이 ] - DP
#include <iostream> #include <vector> #include <algorithm> using namespace std; int d[100003][4]; int solution(vector<vector<int>> land) { int answer = 0;int N = land.size(); d[0][0] = land[0][0];d[0][1] = land[0][1]; d[0][2] = land[0][2];d[0][3] = land[0][3]; for(int i=1;i<N;i++) { d[i][0] = max(d[i-1][1], max(d[i-1][2], d[i-1][3])) + land[i][0]; d[i][1] = max(d[i-1][0], max(d[i-1][2], d[i-1][3])) + land[i][1]; d[i][2] = max(d[i-1][0], max(d[i-1][1], d[i-1][3])) + land[i][2]; d[i][3] = max(d[i-1][0], max(d[i-1][1], d[i-1][2])) + land[i][3]; } answer = max(d[N-1][0], max(d[N-1][1], max(d[N-1][2], d[N-1][3]))); return answer; }
- key point!
: DP의 핵심인메모제이션(memoization)
을 사용해야 한다
Author And Source
이 문제에 관하여(rogramers : 땅따먹기 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/Programers-땅따먹기-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)