백준 #2565 전깃줄

오늘은 동기 김재원과 카페에서 만났다. 함께 한 문제를 풀어보기로 하였는데, 역시 김재원이 먼저 풀었다. 이게 바로 그 문제이다. 백준 2565번. DP를 이용하여 푸는 문제인데, 나는 초반 접근을 잘못해서 해맸다. 요즘 DP라는 드라마가 유행이라, 이제 DP를 대표하는 단어가 다이나믹 프로그래밍이 아니게 되어 조금 아쉽다.. 드라마는 재밌었다!

 

우선 이 문제는 사실 백준 11053 가장 긴 증가하는 부분 수열 문제와 매우 유사하다. 

 

우선 처음에 난 전봇대의 제일 밑에서부터 시작해 겹치는 점의 개수를 2차원배열에 저장한 후 없앴을 때와 있을 때를 dp로 계산해보려 했지만 실패했다. 

 맞게 생각한 풀이는, 시작점과 도착점을 pair 로 vector에 다 저장한 후, 첫번째를 기준으로 오름차순으로 정렬을 하면, 두번째(도착점) 이 만약 중간에 감소하게 된다면 반드시 겹치는 점이 하나 생기게 된다. 따라서, 이때 시작점을 기준으로 정렬된 벡터의 도착점(두번째 원소) 들 중 가장 긴 증가하는 부분 수열을 찾으면 되는 것이다!

 

다음이 코드이다! 

수열을 찾는 dp 코드는 가장 긴 증가하는 부분 수열의 코드와 거의 완전히 동일하기 때문에 따로 설명하진 않겠다. 다음 번, 가장 긴 증가하는 부분 수열 문제 풀이에서 좀 더 자세히 다뤄 볼 수 있도록 하겠다.

 

주말에 재원이형과 오랜만에 놀기로 했다. 알바를 그만 둔 첫 주말을 김재원에게 투자하는 건데 보람있는 시간이 될 지 모르겠다!