[프로그래머스/Lv2] 땅따먹기

문제

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

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

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

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

 

예를 들어,

|1| |2| |3| |5|

|5| |6| |7| |8|

|4| |3| |2| |1|

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

 

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 반환하는 함수를 만들어야 한다.

 

 

제한사항

1. 행의 개수 N : 100,000 이하의 자연수

2. 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어진다.

3. 점수 : 100 이하의 자연수

 

 

코드

def solution(land):
    def find_max(score, i):
        i_score = list(zip(score, range(len(score))))
        sorted_i_score = sorted(i_score, key=lambda x:x[0], reverse=True)

        for iscore in sorted_i_score:
            if iscore[1] != i:
                return iscore[0]
    
    for i in range(len(land)-1):
        for j in range(len(land[i+1])):
            land[i+1][j] += find_max(land[i], j)

    return max(land[-1])

 

 

설명

def solution(land):
    check = -1
    answer = 0
    for score in land:
        i_land = list(zip(score, range(len(score))))
        sorted_i_land = sorted(i_land, key=lambda x:x[0], reverse=True)

        if check != -1:
            for score in sorted_i_land:
                if score[1] != check:
                    answer += score[0]
                    check = score[1]
                    break
        else:
            answer += sorted_i_land[0][0]
            check = sorted_i_land[0][1]

    return answer

처음 제출한 코드인데, 모든 케이스에서 틀리길래 내가 아는 방법으론 풀지 못하겠다 싶어서

다른 사람들의 팁과 풀이를 찾아보고 문제를 풀었다.

 

결론부터 말하자면, 이 문제는 동적 계획법으로 풀어야 한다고 한다.

위 코드처럼 단순히 위에서 아래로 인덱스가 겹치지 않는 가장 큰 수를 더하면 정답이 나오지 않는다.

 

아래의 방법으로 문제를 새로 풀어볼 것이다.

 

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

주어진 땅이 이렇게 초기화되어 있다고 하자.

 

4	3	2	1

아래의 빈칸을 채울 건데, 주어진 땅에서 두번째 행(2, 2, 2, 1)과 첫번째 행(4, 3, 2, 1)을 비교한다.

 

4	3	2	1
5

두번째 행의 첫번째 원소(2)와 같은 순서인 첫번째 행의 (4)를 제외하고 나머지 중에서 가장 큰 값(3)을 더해 빈 칸에 채워넣는다.

 

4	3	2	1
5	6

두번째 행의 두번째 원소(2)와 같은 순서인 첫번째 행의 (3)을 제외하고 나머지 중에서 가장 큰 값(4)를 더해 빈 칸에 넣는다.

 

4	3	2	1
5	6	6	5

나머지 칸에서 같은 작업을 반복한다.

 

4	3	2	1
5	6	6	5
12	12	12	10

주어진 땅의 세번째 행과 새롭게 만들어진 두번째 행에서 위 작업을 반복한다.

 

4	3	2	1
5	6	6	5
12	12	12	10
20	19	18	17

마찬가지로 주어진 땅의 네번째 행과 새롭게 만들어진 세번째 행에서 작업을 반복하면

이런 표가 만들어 진다.

 

표의 모든 칸이 채워지면 가장 마지막 행에서 최대값이 땅따먹기에서 가장 높게 얻을 수 있는 점수를 의미하게 된다.

 

이 과정을 코드로 구현하면 된다.

 

def find_max(score, i):
    i_score = list(zip(score, range(len(score))))
    sorted_i_score = sorted(i_score, key=lambda x:x[0], reverse=True)

    for iscore in sorted_i_score:
        if iscore[1] != i:
            return iscore[0]

i번째 인덱스를 제외한 나머지에서 최대값을 찾아 반환하는 함수이다.

정렬하기 전의 인덱스를 기록해놓기 위해 zip을 이용해서 새로운 배열 i_score를 만들어 둔다.

i_score를 내림차순으로 정렬한다.

 

정렬한 배열 sorted_i_score에서 원소를 하나씩 꺼내며 반복한다.

만약 iscore의 두번째 원소(기록한 인덱스)가 i와 다르다면 즉시 iscore의 첫번째 원소(값)를 반환한다.

 

for i in range(len(land)-1):
    for j in range(len(land[i+1])):
        land[i+1][j] += find_max(land[i], j)

위의 점수 기록 과정을 반복문 두개로 나타낸 것이다.

 

return max(land[-1])

land의 마지막 행에서 최대값을 찾아 반환한다.

---

참고1 : https://school.programmers.co.kr/questions/11755

프로그래머스

참고2 : https://shanepark.tistory.com/183

피보나치 수열과 프로그래머스 땅따먹기 문제로 알아보는 Dynamic Programming (동적 프로그래밍)