땅따먹기

아래 문제는 프로그래머스에서 제공하는 땅따먹기의 문제입니다🧑🏻‍💻

문제 제시

 

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(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],[5,6,7,8],[4,3,2,1]]

16

문제 해결

import Foundation

func solution(_ land:[[Int]]) -> Int{
    var answer = land
    var result = 0

    for i in 1..<land.count {
        answer[i][0] += max(answer[i-1][1], answer[i-1][2], answer[i-1][3])
        answer[i][1] += max(answer[i-1][0], answer[i-1][2], answer[i-1][3])
        answer[i][2] += max(answer[i-1][0], answer[i-1][1], answer[i-1][3])
        answer[i][3] += max(answer[i-1][0], answer[i-1][1], answer[i-1][2])
    }
    result = answer.last!.max()!

    return result
}

사용된 개념

 - 반복문

 - 완전탐색

 

문제 뒷담화

해당 문제는 완전 탐색으로 경우의 수를 생각하는 문제였다.

우선 land와 같은 2차원 배열을 answer로 만들어준다.

그리고 반복문을 두번째 행부터 돌면서 겹치지 않는 이전 행의 값들중 최대값을 추가해준다.

그리고 해당 2차원 배열에 값을 누적해서 변경해준다.

다 돌고 난 후 마지막 인덱스의 최대값을 구하면된다.