[프로그래머스][LV.2] 땅따먹기 | python3

 

문제 링크: 땅따먹기

 

문제 설명

문제 설명

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

 

---

문제 풀이

값을 더하면서 구해야 될 것 같은데 경우의 수를 다 구하자니 시간도 너무 오래걸리고 코드 작성부터가 for문이 엄청 나올 것 같았다. 
그럼 처음부타 다음 행의 가장 큰 값을 가지는 것을 선택해서 더하는 방식은 어떨까 싶었는데 그럼 다다음에 선택하지 못하는 곳에 완전 큰 값이 있으면 값을 구하지 못하고...그리고 선택하면 안되는 경우의 구현을 어떻게 할지 감이 안잡혔다.
그래서 마지막줄에서부터 올라가면서 계산하는건 어떤가 싶었는데 그 경우에도 선택하면 안되는 경우의 구현을 모르겠어서....결국 질문하기의 글들을 참고하여 풀었다..

두(인덱스 1)번째 행부터 기준으로 그 전 꺼를 비교해서 더하는 방식이다.

[ a1, a2, a3, a4 ]  -> 0번째행
[ b1, b2, b3, b4 ]   -> 1번째행
1번째행을 기준으로 큰값을 찾아 더한다.

예를 들어 b1이 기준이면 b1에는 max(a2,a3,a4)의 값을 더해준다. 각각의 max값을 a로 통일하면 
[b1+a, b2+a, b3+a, b4+a] 가 된다. 그럼 이제 다음을 기준으로 같은 일을 반복한다

[b1+a, b2+a, b3+a, b4+a] -> i 행
[c1, c2, c3, c4 ] -> i+1행

c1을 기준으로 c1에는 max(b2+a, b3+a, b4+a) 값을 더해준다.
c2,c3,c4도 반복.

이런식으로 풀면 간단하게 같은 열을 연속으로 밟을 수 없다는 조건을 만족할 수 있다.

 

내코드

def solution(land):
    answer = 0
    a,b,c,d=land[0]
    land=land[1:]
    for l in land:
        e,f,g,h=a,b,c,d
        a,b,c,d=l
        a += max(f,g,h)
        b += max(e,g,h)
        c += max(e,f,h)
        d += max(e,f,g)
        
    return max(a,b,c,d)

 

 

---

다른사람풀이

def solution(land):

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

    return max(land[-1])

같은 논리인데 풀이 방법이 다르다. 리스트 인덱스를 활용하여 푼 풀이방법. 열값하나만 빠지는 거라 간단하게 표현할 수 있다.