99클럽 코테 스터디 4기 32일차 TIL - 백준: 가장 긴 바이토닉 부분 수열(11054) Swift & Python

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
백준	11054	가장 긴 바이토닉 부분 수열	DP	골드4	Swift, Python

🚀 나의 접근 방법

이 문제는 가장 긴 증가하는 부분 수열 문제의 활용이라 보면 된다. 이 문제를 안 풀어 봤다면 먼저 풀어보고 오는 것을 추천한다.

위 문제를 해결하고 왔다면 DP(다이나믹 프로그래밍)를 활용해 가장 긴 증가하는 부분 수열 찾을 수 있을 것이다.

이 문제의 핵심 해결 아이디어는 오름 차순으로 증가하는 부분과 내림차순으로 감소하는 부분을 따로 구해 합하는 것이다.

Int 배열 upCache, downCache를 정의한다.

upCache에 가장 긴 증가하는 부분 수열의 DP 테이블을 저장한다.
그리고 downCache에 가장 긴 감소하는 부분 수열의 DP 테이블을 저장하면 되는데, 필자는 입력되는 배열 A를 reverse 해서 가장 긴 증가하는 부분 수열의 DP 테이블을 구하고 테이블을 reverse 했다.

upCache와 downCache의 각 인덱스를 더하면 증가하는 바이토닉 부분 수열의 dp 테이블을 얻을 수 있다. 이 테이블에서 max 값이 답이 된다.

✍️ 나의 코드

Swift

let N = Int(readLine()!)!
var A = readLine()!.split(separator: " ").map{ Int($0)! }

func dp(array: [Int]) -> [Int] {
    var cache = Array(repeating: 1, count: N)
    for i in 0..<N {
        for j in 0..<i {
            if array[i] > array[j] {
                cache[i] = max(cache[i], cache[j] + 1)
            }
        }
    }
    return cache
}

var upCache = dp(array: A)
A.reverse()
var downCache = dp(array: A)
downCache.reverse()

var maxResult = 0
for i in 0..<N {
    maxResult = max(maxResult, upCache[i] + downCache[i] - 1)
}
print(maxResult)

Python

N = int(input())
A = list(map(int, input().split()))

def dp(array):
    cache = [1] * N
    for i in range(N):
        for j in range(i):
            if A[i] > A[j]:
                cache[i] = max(cache[i], cache[j] + 1)
    return cache

upCache = dp(A)
A.reverse()
downCache = dp(A)
downCache.reverse()

maxResult = 0
for i in range(N):
    maxResult = max(maxResult, upCache[i] + downCache[i] - 1)
print(maxResult)

🤔 회고

이전에 연습했던 문제를 통해 아무 도움 없이 문제를 해결할 수 있었다!! 역시 차근차근 문제를 해결해 나가니 성장하는 것 같다. 앞으로도 파이팅!!