백준 1365번 꼬인 전깃줄

문제

공화국에 있는 유스타운 시에서는 길을 사이에 두고 전봇대가 아래와 같이 두 줄로 늘어서 있다. 그리고 길 왼편과 길 오른편의 전봇대는 하나의 전선으로 연결되어 있다. 어떤 전봇대도 두 개 이상의 다른 전봇대와 연결되어 있지는 않다.

문제는 이 두 전봇대 사이에 있는 전깃줄이 매우 꼬여 있다는 점이다. 꼬여있는 전깃줄은 화재를 유발할 가능성이 있기 때문에 유스타운 시의 시장 임한수는 전격적으로 이 문제를 해결하기로 했다.

임한수는 꼬여 있는 전깃줄 중 몇 개를 적절히 잘라 내어 이 문제를 해결하기로 했다. 하지만 이미 설치해 놓은 전선이 아깝기 때문에 잘라내는 전선을 최소로 하여 꼬여 있는 전선이 하나도 없게 만들려고 한다.

유스타운 시의 시장 임한수를 도와 잘라내야 할 전선의 최소 개수를 구하는 프로그램을 작성하시오.


문제풀이

사용한 알고리즘 : LIS ( DP )

(0) 생각

 잘 생각해보면 최장 증가 순열을 찾는 문제와 같습니다.... (LIS 문제)
 LIS 문제풀이 2가지 중 DP를 활용한 풀이를 사용하였습니다.

(1) 코드 11~19

 i번째 수를 탐색할 때,
    1. vector에 저장된 가장 큰 수 ( 가장 뒤에 수 ) 보다 큰 경우 vector 뒤에 i번째 수를 붙입니다.
    2. 그렇지 않은 경우 lower_bound 를 활용하여 vector에 i번째 이상의 수 중 가장 작은 수를 i번째 수로 바꿔줍니다.

(2) 코드 20

 탐색이 끝난 후 vector 의 크기가 구하고자 하는 최장 증가 부분수열 입니다.
 따라서 전체 N에서 해당 수를 뺀 값이 답이겠죠.

(3) 이해

 이 코드가 왜 돌아가는지 예를 통해 생각해보겠습니다.
 Input:
 8
 1 6 2 5 7 3 5 6
 이 주어졌다고 생각해보겠습니다.

 먼저 vector 하나 만들어 놓습니다.

0
1
2
3
4
5
6
7
입력
1
6
2
5
7
3
5
6
Vector









탐색 순서대로 가겠습니다.
( 탐색 중 vector에는 항상 오름차순으로 저장되게 될 수 밖에 없습니다. )

    1) 0번째 수를 보게 되면, vector는 비어 있기 때문에 그냥 넣어줍니다.

0
1
2
3
4
5
6
7
입력
1
6
2
5
7
3
5
6
Vector
1








    2) 1번째 수를 보면, vector의 마지막 수보다 크니 vector에 추가해줍니다.

0
1
2
3
4
5
6
7
입력
1
6
2
5
7
3
5
6
Vector
1
6







    3) 2번째 수를 보면, vector의 마지막 수보다 크지 않습니다.
       그렇다면 2번째 수보다 크거나 같은 수 중, 가장 작은 수를 찾아줍니다.
       이 경우 1번째 수인 6 이겠네요. 이를 2로 바꾸어 줍니다.
       이게 무슨 의미이냐면, 1, 6 이든 1,2 이든 길이 2인 증가 수열입니다.
       1,6 은 이후 6보다 큰 수가 있어야 길이 3인 증가 수열을 만들 수 있지만,
       1,2 는 이후 2보다 큰 수만 있으면 길이 3인 증가 수열을 만들 수 있습니다.
       따라서 6보다 더 유리한 2로 바꾸어주는 것입니다.

0
1
2
3
4
5
6
7
입력
1
6
2
5
7
3
5
6
Vector
1
2







     이후는 위 과정의 반복입니다.

     4) 3번째 수를 보면 5 입니다. vector의 마지막 수보다 크니 붙여줍니다.

0
1
2
3
4
5
6
7
입력
1
6
2
5
7
3
5
6
Vector
1
2
5






     5) 4번째 수를 보면 7이니 vector의 마지막 수보다 큽니다. 붙여줍니다.

0
1
2
3
4
5
6
7
입력
1
6
2
5
7
3
5
6
Vector
1
2
5
7





     6) 5번째 수를 보면 3이네요. vector에서 3 이상의 가장 작은 수를 찾아줍니다.
        vector의 2번째 수 5가 3 이상의 가장 작은 수이네요. 이를 3으로 바꾸어줍니다.

0
1
2
3
4
5
6
7
입력
1
6
2
5
7
3
5
6
Vector
1
2
3
7





    7) 6번째 수를 보면 5네요. vector의 3번째 수 7이 5 이상의 가장 작은 수 입니다.

0
1
2
3
4
5
6
7
입력
1
6
2
5
7
3
5
6
Vector
1
2
3
5





    8) 7번째 수를 보면 6 입니다. vector의 마지막 수보다 크니 붙여줍니다.

0
1
2
3
4
5
6
7
입력
1
6
2
5
7
3
5
6
Vector
1
2
3
5
6




 이로써 1 6 2 5 7 3 5 6 의 최장 증가 부분수열은 1 2 3 5 6 인걸 알 수 있습니다.
 길이는 5 겠네요.
 답은 8 - 5 = 3 이 됩니다.
 output:
 3



댓글

댓글 쓰기

긴 글 읽어주셔서 감사합니다.
궁금한게 있으시다면 댓글 달아주세요!