junow programmers 땅따먹기

[Junow]

12913. 땅따먹기

링크

메모리 (KB)	시간 (ms)

설계

N 100000 이기때문에 dfs 로 모두 탐색해보면 4 * 3^99999 ?? 번의 탐색을 할거같음.

문제조건보고 n-queen 문제가 생각나서 백트랙킹인줄 알고 dfs 로 풀어봤는데 다 시간초과나옴

질문 게시판보고 dp 인걸 알아챔;

[i][j] 번 땅을 먹을때 가장 큰 점수로 먹는 방법은 j 번 을 제외한 [i-1] 번의 땅들 중 가장 큰 값을 취하는것.

for (int i = 1; i < R; i++) {
  dp[i][0] = land[i][0] + max(dp[i - 1][1], max(dp[i - 1][2], dp[i - 1][3]));
  dp[i][1] = land[i][1] + max(dp[i - 1][0], max(dp[i - 1][2], dp[i - 1][3]));
  dp[i][2] = land[i][2] + max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][3]));
  dp[i][3] = land[i][3] + max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][2]));
}

시간복잡도

N = 행의 개수 N * 4 O(N)