[BOJ/2565/Golang] 백준 2565 - 전깃줄

접근 방식

처음에는 점화식을 어떻게 세워야 할 지 매우 고민했습니다. D[i][j] = (i, j)를 연결할 때 삭제 되어야 할 전선의 최소 개수라고도 세워보고, D[i] = i 번째 전깃줄까지 교차줄이 없게하는 최소 삭제 전깃줄의 개수로도 접근해봤습니다. 아무래도 문제가 풀리지 않아, 처음부터 그림을 그려가며, 그 순서를 살펴봤는데요.

어째 보면 볼수록 가장 긴 증가하는 부분 수열의 길이를 구하는 문제와 비슷해보이는 겁니다. 즉, 없애야 하는 전깃줄의 최소 개수를 구한다는 것은, 전체 전깃줄의 개수에서 남아 있어도 되는 전깃줄의 최대 개수를 뺀 값과 일치한다는 것을 발견한 겁니다!

없애야 하는 전깃줄의 최소 개수 = (전체 전깃줄의 개수) - (교차하지 않고 남아 있어도 괜찮은 전깃줄의 최대 개수)

따라서, 입력 받은 값을 A 전봇대의 위치를 기준으로 오름차순으로 정렬하여 B 전봇대의 위치에 적힌 수열을 받아옵니다. 그리고 해당 수열을 가지고 가장 긴 증가하는 부분 수열의 길이를 찾습니다. 그리고 전체 전깃줄의 개수인 수열의 전체 길이에서 방금 구한 가장 긴 증가하는 부분 수열의 길이를 빼주면 정답을 얻어낼 수 있습니다.

비록 실버 1에 해당하는 문제이긴 하지만, 직접 연관성이 있는 문제를 떠올리고 풀어냈다는게, 그동안의 연습이 헛되지 않은 것 같아 기쁩니다. 접근 방식이 많이 서툴 수 있지만, 이 문제를 찾아 보고 계신 여러분들과 함께 성장하고 있는 중이라고 생각해주셨으면 좋겠습니다 🙂

점화식

점화식이랄 것은 없고, 사실상 가장 긴 증가하는 부분 수열의 길이를 구하는 점화식과 일치합니다. 본 점화식이 이해가 가지 않는다면, 가장 긴 증가하는 부분 수열 문제를 먼저 풀어보시는 것을 추천드립니다.

for i := 1; i <= N; i++ {
    D[i] = 1
    for j := 1; j < i; j++ {
        if A[i] > A[j] {
            D[i] = max(D[i], D[j]+1)
        }
    }
}

코드

package main

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

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

var (
    A []int
    P []pair
    D []int
    N int
)

type pair struct {
    A, B int
}

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

func main() {
    defer w.Flush()
    N = scan()
    P = make([]pair, N)
    A = make([]int, N+1)
    D = make([]int, N+1)
    for i := range P {
        P[i] = pair{
            A: scan(),
            B: scan(),
        }
    }
    sort.Slice(P, func(i, j int) bool {
        return P[i].A < P[j].A
    })
    for i := range P {
        A[i+1] = P[i].B
    }
    for i := 1; i <= N; i++ {
        D[i] = 1
        for j := 1; j < i; j++ {
            if A[i] > A[j] {
                D[i] = max(D[i], D[j]+1)
            }
        }
    }
    fmt.Fprintln(w, N-max(D...))
}

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

func max(arr ...int) int {
    res := arr[0]
    for i := range arr {
        if res < arr[i] {
            res = arr[i]
        }
    }
    return res
}

마무리

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

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