문제

https://programmers.co.kr/learn/courses/30/lessons/12913

문제 설명

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

제한사항

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

입출력 예

land	answer
[[1,2,3,5],[5,6,7,8],[4,3,2,1]]	16

---

Approach #1

   0 1 2 3
   -------
0  1 2 3 5
1  5 6 7 8
2  4 3 2 1

[0][3] -> [1]

  1 2 3 5       
  10 11 12 11  dp[1][j] = land[i-1][0~3중 j빼고]+land[i][j]
  0 0 0 0
5->7->4 : 16

0,0 1을 택했을때, 갈수 있는 선택지 
1,1, 1,2, 1,3 dp에 기록해둠.

Solution #1

function solution(land) {
    var answer = 0;
    let dp = Array.from({length: land.length}, () => new Array(land[0].length).fill(0));
    
    // base case
    for(let i=0; i<4; i++){
        dp[0][i]=land[0][i];
    }
    
    for(let i=1; i<dp.length; i++){
        for(let j=0; j<4; j++){
            let choiceLand = dp[i-1][j];
            
            for(let k=0; k<4; k++){
                //j가 0이라면 1,2,3만 택하고 싶다.
                if(j===k) continue;
                dp[i][k] = Math.max(dp[i][k], choiceLand+land[i][k]);
            }
        }
    }
    
    for(let i=0; i<4; i++){
        answer = Math.max(answer, dp[dp.length-1][i]);
    }

    return answer;
}

N: land.length(행의 개수)

Time Complexity

O(N)

dp 배열 base case 첫번째 for문 : O(4)
dp 배열 채우는 두번째 for문: O(N x 4 x 3)
최종 max 확인하는 세번째 for문: O(4)
=> O(4) + O(N x 4 x 3) + O(4)
=> O(1) + O(N) + O(1)
=> O(N)

Space Complexity

O(N)

dp배열의 크기: O(N*4)
=> O(N)

Review

• dp 문제 풀어본 경험이 있어서인지, 문제 읽은 후에 이거 dp로 풀면 되겠다! 접근은 좋았다. 칭찬해 ~~~
• 속도가 좀 느려서 리팩토링 필요할듯 싶다. ㅠ
  왜 느릴까?
• dp 배열을 굳이 만들었어야 했나..? 그냥 land에서 값 더해줘도 될것 같은데..

---

Approach #2

   0 1 2 3
   -------
0  1 2 3 5
1  5 6 7 8
2  4 3 2 1

0번 행은 그대로 두고, 1번행부더 시작한다.
1번행의 0,1,2,3번째 열의 값을 채울때를 생각해보자.

   0   1  2  3
   -------
0  1   2  3  5
1  10 11 12 11
2  16 15 14 13

land[i][0]에 값을 더해줄때, 나는 land[i-1]의 1,2,3행에서 값을 가져와 더해줄수 있다. 이때 1,2,3행중 max값을 더해주면 될것이다.
land[i][1],
land[i][2],
land[i][3],을 채울때에도 마찬가지.

최종 답: 마지막 행의 최댓값을 리턴.

Solution #1이 optimal 코드는 아닌것 같아 리팩토링한 코드이다. 로직은 위와같다.

Solution #2

function solution(land) {
    var answer = [];
    for(let i=1; i<land.length; i++){
        land[i][0] += Math.max(land[i-1][1], land[i-1][2], land[i-1][3]);
        land[i][1] += Math.max(land[i-1][0], land[i-1][2], land[i-1][3]);
        land[i][2] += Math.max(land[i-1][1], land[i-1][0], land[i-1][3]);
        land[i][3] += Math.max(land[i-1][1], land[i-1][2], land[i-1][0]);
    }
    
    answer = land[land.length-1];

    return Math.max(...answer);
}

Time Complexity

O(N)

Space Complexity

O(1)

answer 배열 크기가 O(4)
=> O(1)

Review

• memoization, bottom-up approach