[Swift] BOJ 1932 정수 삼각형

BOJ 1932 정수 삼각형

 

✅ dp를 이용한 문제였는데, 스스로 점화식을 찾아서 풀었다~!

처음으로 점화식을 찾아서 푼 문제라 엄청 뿌듯하기도 하고, 점화식을 찾는데도 시간이 꽤 걸렸지만 너무나도 행복하다 ㅎㅎ

solved.ac 이용해서 난이도 확인해 봤는데 실버1이라니.. ㅎ

근데 시간을 더 올리는게 중요하겠음.

 

어떻게 풀었냐면 아래 사진을 참고하면 좋을듯하다.

 

🟠 예전에 어떤 글을 보다가 알고리즘 잘하는 사람은 손으로 안하고 머리로만 딱 해서 하는게 진짜 잘하는 사람이라는 글을 봤었는데, 그래서 일부러 종이를 안쓰고 머리속으로 생각하는 연습을 함.

근데 나는 아직 그정도가 아니라서 종이를 쓰면서 하는게 더 낫겠음.

 

🟠

dp값을 지정할 때, 나는 주로 dp[1]과 dp[2]를 먼저 세팅해주는데, 문제의 범위가 1 이상일경우 dp[2]를 초기세팅하는 과정에서 컴파일 에러가 발생함 -> 백준에서 컴파일 에러로 주로 보내줌

또 하나는 optional로 print값이 출력되는 문제인데, 이도 언래핑 해줘야 함. 안그러면 틀렸다고 나옴

 

손으로 하다보니까 패턴을 찾음 ㅎㅎ

 

🟠 코드

        let input: Int = Int(readLine()!)!
        var list = [[Int]]()
        var dp = [[Int]](repeating: [Int](repeating: 0, count: input), count: input)
        
        for _ in 0..<input {
            let v = readLine()!.components(separatedBy: " ").map { Int($0)! }
            list.append(v)
        }
//        print(list)
        dp[0][0] = list[0][0]
        
        if input >= 2 {
            dp[1][0] = dp[0][0] + list[1][0]
            dp[1][1] = dp[0][0] + list[1][1]
        
            for row in 2..<list.count {
                list[row].enumerated().forEach {
                    let col = $0.offset
                    if col == 0 { // 처음
                        dp[row][col] = dp[row-1][0] + list[row][0]
                    } else if col == list[row].count-1 { // 끝
//                        print("끝입니다. \(col)")
                        dp[row][col] = dp[row-1][col-1] + list[row][col]
                    } else {
                        let pivot = max(dp[row-1][col-1], dp[row-1][col])
                        dp[row][col] = pivot + list[row][col]
                    }
                }
            }
        }
        
        print(dp.last!.max()!)