처음에 생각한 풀이는 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를 사용하면 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()!
}