[Level 2] 땅따먹기

 

 

 

Algorithm

-  땅따먹기 -

 

---

 

문제

땅따먹기 게임을 하려고 합니다.

땅따먹기 게임의 땅(land)은 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다.

1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행이 4칸 중 한칸만 밟으면서 내려와야 합니다.

단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

 

예를 들면,

| 1 | 2 | 3 | 5 |
| 5 | 6 | 7 | 8 |
| 4 | 3 | 2 | 1 |

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

 

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최댓값을 리턴하는 함수를 완성해주세요.

 

입출력 예시

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

 

문제 풀기

와... 사실 이문제는 레벨2짜리 문제가 아닌것 같다...ㅋㅋㅋ

 

딱 문제를 읽었을 때에는 이전 인덱스값을 담을 수 있는 변수 index를 만들고 반복문을 통해서 이전 인덱스값과 같지 않게 코드를 작성해서 result안에 값을 누적시켜서 결과값을 리턴하면 해결될 수 있는 문제라고 생각했는데 내가 작성한 코드는 한 행에 있는 값들이 중복되는 값이 없을 경우에만 해결되는 문제이며 만약 한 행안에 중복값이 존재할 경우엔 바로 탈락되어버리는 코드라는걸 깨달았다.

 

그래서 이 문제에서 규칙을 찾는건 너무 어려울 것 같아서 노가다라도 일단 할수있는 만큼 코드를 작성하다가 내가 작성한 코드에서 길을 잃어서 결국 원점으로 돌아와버리는 행동을 수없이 반복했다...ㅎㅎ

 

결국 이 문제는 내 스스로 해결하지 못했고 수많은 검색을 통해서 그나마 이해되는 선에서 설명해준 제로초님의 해설을 기반으로 문제를 내입맛에 맞게 조금 수정했다.

(여러 해결 방법에 대한 답들이 있었으나 이해지 못했....)

 

문제를 해결하지는 못했지만 일단 내가 이해한 걸 기준으로 글로 작성해 보려고 한다.

 

일단 우리가 여기서 꼭 기억해야 할 점은 다음 행으로 내려올때 같은 열로 내려오면 안된다는 점과 한 행안에는 중복값이 존재할 수 있다는 점이다.

 

제로초님 설명에선 위에서부터 한줄씩 내려오면서 누척 최대점수를 구하면 된다고 작성되어 있었는데 코드를 보면 알 수 있듯이 일단 reduce를 사용해주어야 하기 때문에 초기값을 [0, 0, 0, 0]으로 설정을 해주고 매개변수로 주어진 배열에서 0번째에서 3번째까지의 값들을 각 인덱스에 넣어주는데 그냥 넣어주는 것이 아니라 이중에서 초기값에서 같은 인덱스를 가진 값을 제외한 나머지 값을 중 가장 큰값과 더해서 배열을 계속 업데이트 시켜주는 것이다.

 

이렇게 되면 이들 중 가장 큰 값이 바로 답이 되는 것이다.

 

아직 확실하게 이해가 되는건 아니지만 계속 손코딩을 하면서 이해하도록 노력해봐야 겠다.

(역시 2단계문제가 아니야...)