[Programmers] 땅따먹기

Link : Lv2. 땅따먹기

  • 문제 설명

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

 

  • 문제 풀이

한 행에 하나씩 땅을 밟으며 내려가는데 각 땅에는 숫자가 있고 그 숫자의 합이 최대가 되도록 하는 것이 목적이다.

조건은 앞 행에서 현재 밟은 땅과 같은 열에 있는 땅은 밟을 수 없다.

부분으로 살펴 보면, 첫번째 행과 두번째 행에서 최대 값을 구할 수 있다.

1 2 3 5
10 11 12 11

두번 째 행의 첫번째 열을 기준으로 먼저 살펴보자.

두번째 행의 첫번째 열은 위의 예시에서 5 이며 뒤 행인 첫번째 행에 첫번째 열과는 같은 열이므로

계산이 불가능하다. 두번째 열과는 7, 세번째 열과는 8, 4번째 열과는 10의 값이 된다.

이 중에 가장 큰 값은 10 이므로 두번째 행에서 첫번째 열 까지 선택할 수 있는 최대 값은 10이다.

마찬가지로 나머지 두번째 행에서 두번째 열, 세번째 열, 네번째 열을 모두 구하면 위 그림과 같다.

1 2 3 5
10 11 12 11
16 15 13 13

위 방식으로 한번 더 구하면 세번째 행에서 최대 값을 가지는 열은 첫번째 열이며 값은 16이다.

이런식으로 메모리를 둬서 최대값을 저장하며 문제를 풀면 쉽게 풀릴 것이다.

효율성은 BigO(Row * Col²) 일 테지만 Col = 4 로 상수이므로 BigO(Row)가 될 것이다.

Source Code : hopscotch.cpp

댓글 남기기