[Lv2] 땅따먹기

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

 

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(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

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

 

 

---

 

다음의 경우를 생각해봅니다.

 

| 01 | 02 | 03 | 04 |

| 20 | 16 | 12 | 10 |

| 88 | 38 | 22 | 11 |

 

첫 행 기준 04는 다음 행의 가능한 후보(20, 16, 12) 중 20을 더해야 제일 커질 것 같습니다.

 

하지만 여기서 다다음행의 88은 선택할 수 없고, 38, 22, 11 중 하나를 선택하게 됩니다.(04+20+38=62)

 

04가 20이 아니라 16을 선택했다면, 그 다음 행에서도 88을 선택할 수 있겠죠?(04+16+88=108)

 

단기적인 관점에서 최선의 선택을 했다고해서, 최종 결과도 최대라는 보장은 없습니다.

 

즉, 여러 경우를 살펴봐야 합니다.

 

그래서 이를 토대로 DFS를 하면? 시간초과나 메모리초과가 발생합니다.(단계를 수행할 수록 *3)

 

 

이제 기준을 바꿔봅니다. 우리에게 필요한건 최종 결과값이지, 어느 칸으로 뛴 과정은 필요없으니까요.

 

앞에서는 당연히 시작점인 위에서 아래로 생각했지만,

 

이제 선택받는 아래부터 후보자들(이전 행)을 골라잡는 걸 생각해봅니다.

 

위에서 내려오려면, 첫번째 - 첫칸제외한칸들 - 두번째에서선택한애제외한칸들 - ... 해서 점점 *(칸-1)의 경우로 번져갔습니다. 움직임을 가정하면, 최대값으로의 움직임은 1-3-2-4-1-3-2 처럼 이리저리 뛸 것입니다.

 

아래→위 기준으로는, 첫째칸에 올 수 있는 애들은 2,3,4째 칸의 애들 뿐이고, 두번째칸에 올 수 있는 애들은 1,3,4칸의 애들입니다.

 

이건 절대 기준이 바뀌지 않습니다. 몇 번째 단계이더라도 아래 기준으로 1번째칸에 올 수 있는 애들은 여전히 2,3,4째 칸 애들입니다.

 

문제의 조건은 그대로지만 복잡도가 줄어들었습니다. (위→아래라면 바뀌어가는 현재칸을 계속 기억해야하죠.)

 

| 01 | 02 | 03 | 04 |

| 20 | 16 | 12 | 10 |

| 88 | 38 | 22 | 11 |

 

첫번째 계산은 둘째행(20, 16, 12, 10) 기준으로 첫째행(01, 02, 03, 04)를 봅니다.

 

20으로 올 수 있는 애들(02, 03, 04) 중, 가장 큰 수는 04입니다.

16으로 올 수 있는 애들(01, 03, 04) 중, 가장 큰 수는 04입니다.

12로 올 수 있는 애들(01, 02, 04) 중, 가장 큰 수는 04입니다.

10으로 올 수 있는 애들(01, 02, 03) 중, 가장 큰 수는 03입니다.

 

각 값을 더해줍니다.

 

| 01 | 02 | 03 | 04 |

| 24 | 20 | 16 | 13 |

| 88 | 38 | 22 | 11 |

 

누적시킨 값에 다음 행과 계산합니다. 여전히 기준은 아래 행으로 합니다.

 

88로 올 수 있는 애들(20, 16, 13) 중, 가장 큰 수는 20입니다.

38로 올 수 있는 애들(24, 16, 13) 중, 가장 큰 수는 24입니다.

22로 올 수 있는 애들(24, 20, 13) 중, 가장 큰 수는 24입니다.

11로 올 수 있는 애들(24, 20, 16) 중, 가장 큰 수는 24입니다.

 

각 값을 더해줍니다.

 

이렇게 아래를 기준으로 할 때는 칸을 뛰고 자시고 가능한 애들 중 제일 큰 애만 선택하면 됩니다.

 

어차피 자신에게까지 도달한 후보들은 최대값을 만들면서 그 규칙을 지켜낸 애들이니까요.

 

더해 주면, | 108 | 62 | 46 | 35 | 로, 최대값은 108입니다.

 

 

풀이는 끝났습니다.

int solution(int[][] land) {
    int[] cal = new int[4];
    for(int i=1;i<land.length;i++) {
        for(int j=0;j<4;j++) {
            int max = 0;
            for(int k=0;k<4;k++) {
                if(k!=j) {
                    if(land[i-1][k]>max) max=land[i-1][k];
                }
            }
            cal[j] = land[i][j]+max;
        }
        for(int j=0;j<4;j++) {
            land[i][j] = cal[j];
        }
    }
    int max = 0;
    for(int i=0;i<4;i++) {
        if(cal[i]>max) max=cal[i];
    }
    return max;
}