접근 방식
이 문제는 직전 문제인 LCS (9251) 문제와 동일합니다. 다만 한 가지 더 출력해야 하는데요. 바로 찾은 LCS의 길이 뿐만 아니라, LCS 부분 수열 자체도 출력해야 합니다.
이 문제를 보고 처음 든 생각은, 아 뭔가 부모를 찾고 찾아서 거꾸로 이동하면서 출력하면 되겠구나.. 였습니다. 하지만 부모를 찾아갈 때 어떤 조건을 기준으로 이동할 것인지 생각하는 부분이 어려웠습니다.
중요한 점은 이전에 LCS의 길이가 증가할 때를 살펴보면, [i] == B[j]
인 경우였습니다. 이 경우에 D[i][j] = D[i-1][j-1] + 1
을 이용할 수 있었죠.
부분 수열 자체를 찾기 위한 꼬리에 꼬리를 무는 이동 조건도 이와 유사합니다. 이 전에 D[i-1][j]
또는 D[i][j-1]
은 일치하지 않는 경우에 갖게 되는 값이었습니다. 즉, D[i][j]
의 값이 D[i-1][j]
또는 D[i][j-1]
과 동일하다면, 이는 부분 수열에 해당하지 않는 원소일 겁니다. 그럴 땐 그냥 둘 중 아무 값으로나 이동합니다.
만약 D[i][j]
와 일치하는 값이 둘 중에 없다면, 그 값이야말로 우리가 찾던 부분 수열에 해당하는 원소입니다. 따라서 이를 부분 수열 배열에 넣어줍시다. 그리고 다음으로는 D[i-1][j-1]
로 이동합니다. LCS의 길이를 찾을 때도 LCS에 해당하는 D[i][j]
는 D[i-1][j-1]
에서 찾아왔다는 걸 생각해보면 그 역순으로 이동하고 있다는 것을 알 수 있습니다.
이렇게 쭉 이동하다가 i==j==0
이 되면, 이동을 멈추고 그 동안 모아왔던 부분 수열 배열을 역순으로 출력하면, 우리가 찾던 LCS가 출력 되는 것을 확인할 수 있습니다.
저는 부분 수열 출력을 위한 배열을 만드는 건, 위에서부터 아래로(Top→Down)으로 이동하기 때문에 재귀가 접근하기 쉬울 것으로 판단하고 아래와 같이 코드를 작성했습니다. solve()
메서드를 참고해주세요 🙂
solve()
메서드
func solve(i, j int) {
if D[i][j] == 0 {
return
}
if D[i][j] == D[i-1][j] {
solve(i-1, j)
} else if D[i][j] == D[i][j-1] {
solve(i, j-1)
} else {
result = append(result, string(A[i]))
solve(i-1, j-1)
}
}
코드
package main
import (
"bufio"
"fmt"
"os"
)
var (
w = bufio.NewWriter(os.Stdout)
sc = bufio.NewScanner(os.Stdin)
)
var (
D [][]int
)
func main() {
defer w.Flush()
A, B := " "+scan(), " "+scan()
lenA, lenB := len(A), len(B)
D := make([][]int, lenA)
for i := range D {
D[i] = make([]int, lenB)
}
answer := 0
for i := 1; i < lenA; i++ {
for j := 1; j < lenB; j++ {
if A[i] == B[j] {
D[i][j] = D[i-1][j-1] + 1
} else {
D[i][j] = 0
}
if answer < D[i][j] {
answer = D[i][j]
}
}
}
fmt.Fprintln(w, answer)
}
func scan() string {
sc.Scan()
return sc.Text()
}
마무리
여기까지 따라오시느라 고생 많으셨습니다. 만약 이 글이 도움이 되셨다면 글 좌측 하단의 하트❤를 눌러주시면 감사하겠습니다.
혹시라도 글에 이상이 있거나, 이해가 가지 않으시는 부분, 또는 추가적으로 궁금하신 내용이 있다면 주저 마시고 댓글💬을 남겨주세요! 빠른 시간 안에 답변을 드리겠습니다 😊
'PS > BOJ' 카테고리의 다른 글
[BOJ/12969/Golang] 백준 12969 - ABC (0) | 2021.05.24 |
---|---|
[BOJ/14238/Golang] 백준 14238 - 출근 기록 (0) | 2021.05.23 |
[BOJ/2565/Golang] 백준 2565 - 전깃줄 (0) | 2021.05.20 |
[BOJ/5557/Golang] 백준 5557 - 1학년 (0) | 2021.05.19 |
[BOJ/9252/Golang] 백준 9252 - LCS 2 (0) | 2021.05.18 |