백준 가장 긴 증가하는 부분 수열4 (Python/Go)

문제 링크: www.acmicpc.net/problem/14002

14002번: 가장 긴 증가하는 부분 수열 4

 

LIS 문제인데 단순 개수만 구하는게 아닌 어떤 원소들로 이루어져있는지도 출력해야하는 문제입니다.

기본적인 LIS 코드는 아래와 같습니다. dp를 0이 아닌 1로 초기화하는 것에 주의해야합니다. 자기 자신을 포함하기 때문에 1로 초기화 해야합니다.

n = int(input())
nums = list(map(int, input().split()))
 
dp = [1] * n     # 길이를 나타내는 dp, 예를들어 dp[5] = 4라면 nums[5]를 마지막으로 하고 길이가 총 5임
 
 
for i in range(n):
    for j in range(i):
        if nums[j] < nums[i]:
            dp[i] = max(dp[i], dp[j]+1)
 
print(max(dp))

 

각 수열을 이루는 원소를 찾기 위해 trace라는 이전 인덱스를 나타내는 리스트를 추가해서 구할 것입니다.

문제의 예제인 10, 20, 10, 30, 20, 50으로 trace를 설명해보겠습니다.

num: 10 20 10 30 20 50
dp:     1   2   1   3    2   4
trace: -1  0  -1   1   0   3

각 수열을 이루는 원소는 max(dp)에 해당하는 50을 시작으로 수열을 완성해나가면 됩니다.

표를 보면 50의 이전 인덱스는 3입니다. 그럼 nums[3]에 해당하는 30을 출력하고 다시 30의 이전 인덱스는 1이므로 nums[1]인 20을 출력하는 식으로 구할 수 있습니다. -1이 나오면 종료하면 됩니다. dfs방식으로 구현하면 됩니다.

아래는 파이썬 코드입니다.

def dfs(idx):
    if idx == -1:
        return
 
    dfs(trace[idx])
    print(nums[idx], end=' ')
 
 
n = int(input())
nums = list(map(int, input().split()))
 
dp = [1] * n     # 길이를 나타내는 dp, 예를들어 dp[5] = 4라면 nums[5]를 마지막으로 하고 길이가 총 5임
trace = [-1] * n  # 이전 인덱스를 나타냄
 
for i in range(n):
    for j in range(i):
        if nums[j] < nums[i] and dp[j]+1 > dp[i]:
            dp[i] = dp[j] + 1
            trace[i] = j
 
length = 1
start_idx = 0  # 여기 인덱스부터 시작해서 원소를 구함
for i in range(n):
    if length < dp[i]:
        length = dp[i]
        start_idx = i
 
print(length)
dfs(start_idx)

 

아래는 Go코드입니다.

package main
 
import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)
 
var dp []int
var trace []int
var nums []int
 
func initSlice(dp, trace []int, n int) {
    for i:=0; i<n; i++ {
        dp[i] = 1
        trace[i] = -1
    }
}
 
func changeToInt(s string) []int {
    var numSlice []int
    for _, word := range strings.Fields(s) {
        num, _ := strconv.Atoi(word)
        numSlice = append(numSlice, num)
    }
    return numSlice
}
 
func dfs(idx int) {
    if idx == -1 {
        return
    }
 
    dfs(trace[idx])
    fmt.Printf("%d ", nums[idx])
}
 
func main() {
    var n int
    fmt.Scanln(&n)
 
    dp = make([]int, n)
    trace = make([]int, n)  // 원소 추적용
 
    initSlice(dp, trace, n)  // dp는 1로, trace는 -1로 초기화
 
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Scan()
    numString := scanner.Text()  // numString은 string이라 int배열로 바꿔줘야함
    nums = changeToInt(numString)
 
    for i:=0; i<n; i++ {
        for j:=0; j<i; j++ {
            if nums[i] > nums[j] && dp[i] < dp[j]+1 {
                dp[i] = dp[j] + 1
                trace[i] = j
            }
        }
    }
 
    length := 0  // 최장 길이
    startIdx := 0 // 여기서부터 원소 추적 시작
    for i:=0; i<n; i++ {
        if length < dp[i] {
            length = dp[i]
            startIdx = i
        }
    }
 
    fmt.Println(length)
    dfs(startIdx)
}