백준 2565 - 전깃줄

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

2565번: 전깃줄

이 문제를 푸는 데 여러가지 방법이 존재한다.

그러나 전깃줄이 꼬이지 않았을 경우 B 전깃줄의 번호는 항상 증가한다는 사실을 알아차리면

원래의 문제를 LIS 찾기 문제의 응용으로 바꿀 수 있다.

전깃줄이 꼬이지 않게 하기 위해서는 LIS를 구성하는 전깃줄을 제외하고 모두 없애면 되기 때문이다.

 

다만 이 문제에서는 전깃줄 번호와 전깃줄의 수가 일대일로 대응하지 않는다.

따라서 배열을 생성하고 dp를 적용할 때 이 점을 유념해야한다.

 

ex1)

전깃줄 8개 => int arr[8]

입력값 10 10 => arr[10] = 10

=> OutOfBound

ex2)

전깃줄 2개

입력값 2 4, 5 6

dp 테이블 setup => dp[1] = 1

=> X (답 : dp[1] = 0)

 

 

배운 내용 :

문제의 본질을 찾아내면 배웠던 알고리즘을 활용해 쉽게 풀 수 있다

DP 배열의 range를 매크로로 작성하면 깔끔하다