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