[프로그래머스] 땅따먹기

[프로그래머스] level2 땅따먹기

 

소요시간 : 45분

 

아 진짜... level2로 8점 처음으로 받았다 그리고 드디어 프로그래머스 점수가 1300대를 넘었다

감격해서 캡쳐했는데 날렸다 눈물난다.

 

처음에 N크기 안보고 그냥 dfs문제네 하고 풀었더니 시간초과가 났다.

그래서 N을 봤더니 십만이었다. dfs는 어림도 없었다.

그래서 dp 나 그리디 쪽 일 거라고 생각하고

한참 생각했다.......

아직도 dp 가 익숙하지 않다.. 슬프다

한참 생각하다가 떠올린 방법은,, score 2차원 배열을 만들어서

0행 각 열에 land 점수를 넣어놓고

행을 올리면서 열 4개에 대해 전 행 score 4개와 더해보고 최댓값을 찾는 것이다.

그렇게 하면 마지막 행의 4열 중 제일 큰 값이 정답이 된다.

class Solution {
  int solution(int[][] land) {
    int N = land.length;

    int[][] score = new int[N][4];
    for (int j = 0; j < 4; j++) {		
    	score[0][j] = land[0][j];
    }

    for (int i = 1; i < land.length; i++) {
      for (int j = 0; j < 4; j++) {
        for (int j2 = 0; j2 < 4; j2++) {
          if(j == j2) continue;
          score[i][j] = Math.max(score[i][j], score[i-1][j2] + land[i][j]);
        }
      }
    }

    int max = 0;
    for (int j = 0; j < 4; j++) {
    	if(max < score[N-1][j]) max = score[N-1][j];
    }
    return max;
  }
}