[JavaScript] 백준 2565번 문제 풀이

 

문제 풀이

처음에는 가장 많이 겹치는 순으로 제거하면서 겹치지 않는 선들만 남기려고 헀다.

하지만, 이 접근 방식은 DP와 거리가 있다고 생각을 했고 오히려 Greedy 알고리즘에 가깝다는 생각이 들었다.

DP의 가장 중요한 특성 중 하나인 bottom-up을 고려하여 다시 생각을 해보는 시간을 가졌다.

⇒ 결과적으로 겹치지 않는 경우를 카운트

 

 

첫 번째 줄부터 마지막 줄까지 순차적으로 보면서 겹치는 경우를 고려하려고 했으나 쉽지 않았다.

처음에 입력을 받을 때, 랜덤한 순서로 받기 때문에 오름차순으로 정렬하여 우선 조금 더 쉽게 판단할 수 있도록 했다.

(왼쪽을 기준으로 오름차순 정렬)

오름차순으로 정렬하여 가장 긴 수열(경우)를 찾는 것 = 가장 많이 겹치지 않는 경우

 

오름차순 정렬

겹치지 않는 전깃줄 구해보기

 

코드 과정