[백준/Swift] 2096: 내려가기 | PS일지

문제

2096번: 내려가기

간단한 문제 요약

첫 줄에서 마지막 줄로 내려가는 게임이다. 맨 첫 줄의 시작은 별표의 위치이다. 그리고 각각의 칸에는 숫자가 있다. 위 층(별표)에서 아래층으로 내려갈 수 있는 경우는 각각의 별표 아래 동그라미 친 경우 이다.

마지막 줄로 내려갔을 때 얻을 수 있는 (방문한 칸 숫자 누적 합산)최대, 최소 점수를 구하시오!!

 

문제 풀이, 했갈렸던 점

어떻게 하면 문제를 풀 수 있을까? 고민했습니다. 그래프 형식의 input만 보면 dfs, bfs가 자꾸 생각나네요. dp를 통해 접근해보고 싶었습니다. 요즘 dp를 공부 중인데, dp로 접근하기 위해선 sub problem으로 나눌 수 있어야 하고 맨 처음 계산한 sub problem은 메모제이션 해야한다는 개념을 적용해야 합니다.

 

아래 있는 칸이 최대 값 or 최소  값을 갖기 위해서는 바로 위에 있는 칸들의 영향을 받습니다. 

 

 

왼쪽 그림은 문제에서 설명한 아래로 내려가는 경우의 일부 입니다. 이를 반대로 생각하면 아래로 내려갔을 때 최대 값을 갖기 위해 오른쪽 그림과 같이 위의 두 칸(아래 양 끝 칸인 경우) or 세 칸(아래 가운데 칸일 경우) 중 최대 값과 현재 아래의 칸에 해당하는 숫자를 더해서 저장하면 됩니다.

 

모든 칸에서 최대, 최소 값을 구하기 위해서는 주어진 맵을 전부 한번만 탐색하면 됩니다. ( 위의 사진에서 오른쪽 그림과 같은 경우 초기 라인 탐색x)

 

저는 모든 칸을 원소로 하는 2차원 배열에 누적 값을 증가시켜 나갔습니다. 근데 나중에 다른 분들의 풀이를 보니까 1차원 배열을 사용했습니다. 결국 맵의 위에서 아래로 한 라인씩 탐색하는데 이 결과만 저장하면 아래의 칸을 구할 때 이 칸의 경우 중 최대, 최소만 체크하면 되기 때문입니다. 메모제이션은 prev result에 대해서만 저장해도 충분하다는 것을 알게 되었습니다...

 

코드

var n = Int(readLine()!)!
var res = ""
var board = Array(repeating: [Int](), count: n)

func clearCache() -> [[Int]] {
    var temp = Array(repeating: Array(repeating: 0, count: 3), count: n)
    temp[0] = board[0]
    return temp
}

func input() {
    _=(0..<board.count).map{
        board[$0] = readLine()!.split{$0==" "}.map{Int(String($0))!}
    }
}

func solution() {
    input()
    var cache = clearCache()
    (1..<n).map {
        cache[$0][0] = max(cache[$0-1][0],cache[$0-1][1]) + board[$0][0]
        cache[$0][1] = max(cache[$0-1][0],cache[$0-1][1],cache[$0-1][2]) + board[$0][1]
        cache[$0][2] = max(cache[$0-1][1],cache[$0-1][2]) + board[$0][2]
    }
    res += "\(cache[n-1].max()!) "
    cache = clearCache()
    (1..<n).map {
        cache[$0][0] = min(cache[$0-1][0],cache[$0-1][1]) + board[$0][0]
        cache[$0][1] = min(cache[$0-1][0],cache[$0-1][1],cache[$0-1][2]) + board[$0][1]
        cache[$0][2] = min(cache[$0-1][1],cache[$0-1][2]) + board[$0][2]
    }
    print(res + "\(cache[n-1].min()!)")
}

solution()