Level 2 땅따먹기 Python3

programmers.co.kr/learn/courses/30/lessons/12913?language=python3

코딩테스트 연습 - 땅따먹기

 

최종 코드

• GitHub github.com/hwayeon351/Programmers-Algorithms

def solution(land):
    for i in range(len(land)-1):
        for j in range(4):
            land[i+1][j] += max(land[i][:j]+land[i][j+1:])
    return max(land[-1])

 

---

풀이 과정

풀이 시간 6분

 문제를 풀기까지 이전에 작성했던 틀린 코드가 2개 있었다. 틀린 코드들을 작성하면서 소요한 시간은 45분이었다. 그 결과 모두 틀려버려서 다른 사람의 풀이 방법을 찾아 본 후 힌트를 얻게 되었고 그 방법으로 다시 풀어보니 6분밖에 걸리지 않았다... 그렇게 작성해 낸 코드가 최종 코드와 같다. 틀린 코드에 대한 리뷰는 아래 오답 노트에 작성하도록 하겠다.

여기서는 최종 코드에 대한 풀이 과정을 설명하도록 하겠다.

 

문제 예시 land = [[1,2,3,5],[5,6,7,8],[4,3,2,1]]

 쉽게 이해하기 위해 문제에서 제공한 예시를 통해 설명하도록 하겠다.

먼저, land[0]에서 0번째 값을 제외한 수들 중 가장 큰 값을 land[1][0]에 더해준다. 왼쪽 그림을 보면, land[0]에서 0번째 값을 제외한 수들 중 가장 큰 값은 land[0][3] = 5이다. 즉, land[1][0] += 5를 한 결과, land[1][0] = 10이 된다.

그 다음, land[0]에서 1번째 값을 제외한 수 중 가장 큰 값을 land[1][1]에 더해준다. land[0][3] = 5로 가장 크기 때문에, land[1][1] += 5를 한 결과, land[1][1] = 11이 된다.

마찬가지로, land[1][2]에 land[0]에서 2번째 값을 제외한 가장 큰 수를 더해주어 land[1][2] = 12가 된다.

마지막으로 land[1][3]에 land[0]에서 3번째 값을 제외한 가장 큰 수를 더해주면 land[1][3] = 11이 된다.

 

그 결과, 현재 land는 다음과 같다.

 전과 똑같이, 이번에는 land[2]에서 i번째 값을 제외한 수들 중 가장 큰 값을 land[2][i]에 더해준다.

이를 i in range(4)만큼 반복하면 그 결과 land[3][0] += land[2][2], land[3][1] += land[2][2], land[3][2] += land[2][1], land[3][3] += land[2][2]가 된다.

 

그 결과, 최종 land는 다음과 같다.

마지막 행의 최댓값이 정답이므로 16이 답이다.

 

 

 

이렇게 한 행에서 i번째를 제외한 가장 큰 수를 다음 행의 i번째에 더해주면, 마지막 행에 가능한 최대값을 뽑아 낼 수 있다.

 

 이를 코드로 작성하면 다음과 같다.

def solution(land):
    for i in range(len(land)-1):
        for j in range(4):
            land[i+1][j] += max(land[i][:j]+land[i][j+1:])
    return max(land[-1])

 

 

---

오답 노트

틀린 코드 1

def solution(land):
    answer = 0
    for i in range(4):
        before = i
        sum = land[0][i]
        for j in range(1, len(land)):
            sum += max(land[j][:before] + land[j][before+1:])
            before = land[j].index(max(land[j][:before] + land[j][before+1:]))
        if sum > answer: answer = sum
    return answer

각 열 첫 행에서 출발한다고 생각하고 다음 행으로 갈 때마다 이전에 밟았던 열을 제외한 수 중 가장 큰 값을 밟아간다고 생각하며 짠 코드이다. before은 이전에 밟았던 행의 열 인덱스를 저장한다. 열은 총 4개이므로 for문을 통해 다음과 같은 과정을 4번 반복했다.

1. land의 i번째 열에서 시작하므로 before을 i로 초기화하고, sum은 land의 i열의 0행 값으로 초기화해준다.
2. 첫번째 행부터 마지막 행까지 가야하기 때문에 for문을 range(1, len(land))만큼 반복한다. 이 때 각 행마다 before 열을 제외한 가장 큰 수를 sum에 더해가고 max값의 index를 before에 넣어준다.
3. sum이 answer보다 크면 answer을 sum으로 초기화 해준다.

▶ 결과 = 실패

 문제에서 제시한 테스트 케이스는 통과했지만, 제출하니 모두 실패가 떴다. 곰곰이 생각해보니 각 행의 최댓값이 여러개 있는 경우에 land[j].index()에서 해당 값이 존재하는 첫번째 인덱스를 반환하게 되기 때문에 오답이 발생할 수 밖에 없었다.

 가령, land = [[4, 3, 2, 1], [2, 2, 2, 1], [6, 6, 6, 4], [8, 7, 6, 5]]인 경우,

0열의 2번째 행에서 sum = 4+2 = 6이 되고 이때, before = land[0].index(2) = 0이 되기 때문에 애초에 문제 조건에서도 맞지 않을 뿐더러 결과 값이 19가 출력이 된다. (이 경우, 정답은 20이다.)

따라서, 잘 못 푼 문제이다.

 

 

틀린 코드 2

max_sum = 0
def dfs(cnt, before, sum, land):
    global max_sum
    if cnt >= len(land):
        if max_sum < sum: max_sum = sum
        return
    for i in range(0, 4):
        if i != before:
            dfs(cnt+1, i, sum+land[cnt][i], land)

def solution(land):
    global max_sum
    dfs(0, -1, 0, land)
    return max_sum

DFS를 활용해 문제를 풀었다. before 인덱스를 제외한 수들을 더해주면서 dfs(cnt+1, i, sum+land[cnt][i], land)를 호출했다. cnt가 len(land)이면, max_sum과 sum을 비교해주는 방식이다.

 

▶ 결과 = 실패

 이 역시, 문제에서 제시된 테스트 케이스는 통과했지만, 제출해보니 모두 시간초과가 났다. 행의 개수가 최대 100,000이다 보니 재귀가 너무 깊어져서 시간 초과가 날 수 밖에 없었다.

따라서, 이 역시도 잘못 접근한 방법이었다.