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

🚫 dfs를 활용한 풀이 → 시간초과

처음에 생각한 풀이는 dfs를 활용해서 모든 경우의 수를 구해보는 것이었습니다. 물론 완전 탐색이기 때문에 테스트 케이스는 통과했습니다만 행이 최대 100,000이고 열이 4이므로 모든 경우를 따지려면 4^100,000 번의 탐색이 필요합니다. 무조건 시간초과입니다.

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

    func dfs(_ row: Int, _ col: Int) {
        if row == land.count {
            answer = max(answer, score)
            return
        }

        for i in 0..<4 {
            if i == col {
                continue
            }
            score += land[row][col]
            dfs(row + 1, i)
            score -= land[row][col]
        }
    }

    for i in 0..<4 {
        dfs(0, i)
    }

    return answer
}

✅ dp를 활용한 풀이

문제 풀이 아이디어

생각을 해보면 완전탐색을 할 때 점수가 작은 칸을 밟는 경우는 굳이 탐색할 필요가 없습니다. 따라서 시간복잡도를 줄일 수 있는 다른 방법을 생각해야 합니다.

완전탐색을 하면 안되고 dp를 활용해서 풀어주어야 합니다. dp를 활용해서 특정 행, 열을 밟았을 때 얻을 수 있는 최대 점수를 저장해가면서 풀 수 있습니다. 점화식은 아래와 같습니다.

아래 점화식을 통해 dp를 사용하면 4 * 100,000번의 연산으로 답을 구할 수 있습니다.

정의: dp[i][j] = i행 j열을 "마지막"으로 밟을 때 얻을 수 있는 최대 점수
초기값: dp[0][j] = land[0][j]
점화식: i - 1 행에서 j열을 제외하고 최댓값을 구하고 land[i][j]를 더한다.
	dp[i][0] = max(dp[i - 1][1], dp[i - 1][2], dp[i - 1][3]) + land[i][0]
	dp[i][1] = max(dp[i - 1][0], dp[i - 1][2], dp[i - 1][3]) + land[i][1]
	dp[i][2] = max(dp[i - 1][0], dp[i - 1][1], dp[i - 1][3]) + land[i][2]
	dp[i][3] = max(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]) + land[i][3]
	

코드

func solution(_ land:[[Int]]) -> Int {
    // land를 복사해서 dp에 활용
    var land = land
    
    // i행의 j열을 밟았을 때의 최댓값
        //👉 i - 1행의 j열을 제외한 열을 밟았을 때의 점수 중에 최댓값을 i열 j행의 점수와 더한다
    for i in 1..<land.count {
        for j in 0..<4 {
            // j을 제외한 밟을 수 있는 열 구하기
            var steppable = [Int]()
            for k in 0..<4 {
                if k != j { steppable.append(jj) }
            }
            // 밟을 수 있는 열 중에서 가장 큰 점수 더하기
            land[i][j] += max(land[i - 1][steppable[0]], land[i - 1][steppable[1]], land[i - 1][steppable[2]])
        }
    }
    
    // 마지막 행의 누적된 점수 중에 최댓값을 리턴한다.
    return land[land.count - 1].max()!
}