[BOJ/11053/Golang&Python] 백준 11053 - 가장 긴 증가하는 부분 수열

[BOJ/11053/Golang&Python] 백준 11053 - 가장 긴 증가하는 부분 수열

문제로 이동하기

https://www.acmicpc.net/problem/11053

접근 방식

가장 긴 증가하는 부분 수열은 Longest Increasing Subsequence 라고도 합니다. 줄여서 LIS라고 하는데요. 대표적인 다이나믹 문제입니다. 이 문제는 1차원 배열로도 풀 수 있습니다. 계단수 문제나 123 더하기 5번 문제처럼 2차원 배열을 사용하지 않아도 되는 이유는 이미 있는 수를 사용하기 때문입니다. 즉, 계단수 문제나 123 더하기 5 문제처럼 마지막에 누가 와야할지 알 수 없는 경우에는 마지막에 올 수를 기록하기 위해 이차원 배열을 사용했지만, LIS의 경우, 어떤 수가 오더라도 해당 수는 수열의 일부이므로 숫자를 알 수 있기 때문입니다.

점화식

점화식은 매우 단순합니다.

if i > j && A[i] > A[j] {
    D[i] = max(D[i], D[j]+1)
} 

증가하는 부분 수열이 되기 위해선 먼저 나온 수, 즉 A[j]가 뒤에 나온 수 A[i] 보다 작아야 합니다. 이 조건을 만족할 때 D[i]는 수열의 i번째 숫자를 마지막으로 하는 LIS의 길이를 의미합니다.

코드(Go)

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var (
    w  = bufio.NewWriter(os.Stdout)
    sc = bufio.NewScanner(os.Stdin)
)

func init() {
    sc.Split(bufio.ScanWords)
}

func main() {
    defer w.Flush()
    N := scanInt()
    A := make([]int, N+1)
    D := make([]int, N+1)
    for i := range A {
        if i != 0 {
            A[i] = scanInt()
            D[i] = 1
        }
    }
    for i := 1; i <= N; i++ {
        for j := 1; j < i; j++ {
            if A[i] > A[j] {
                D[i] = max(D[i], D[j]+1)
            }
        }
    }
    res := D[0]
    for i := 1; i <= N; i++ {
        if res < D[i] {
            res = D[i]
        }
    }
    fmt.Fprintln(w, res)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func scanInt() int {
    sc.Scan()
    n, _ := strconv.Atoi(sc.Text())
    return n
}

코드(Python)

import sys; input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().split()]
D = [1 for _ in range(N)]
for i in range(N):
    for j in range(i):
        if A[i] > A[j]:
            D[i] = max(D[i], D[j] + 1)
print(max(D))

여담

여담이지만, 다시봐도 Golang의 코드 길이는 정말 레전드네요 ㅋㅋㅋ

마무리

여기까지 따라오시느라 고생 많으셨습니다. 만약 이 글이 도움이 되셨다면 글 좌측 하단의 하트❤를 눌러주시면 감사하겠습니다.

혹시라도 글에 이상이 있거나, 이해가 가지 않으시는 부분, 또는 추가적으로 궁금하신 내용이 있다면 주저 마시고 댓글💬을 남겨주세요! 빠른 시간 안에 답변을 드리겠습니다 😊