문제 링크
- http://icpc.me/2984
문제 출처
- 2007/2008 COCI Contest #6 6번
사용 알고리즘
- DP
시간복잡도
- $O(N \log N)$
풀이
들어온 나들목의 번호와 나가는 나들목의 번호를 각각 정렬하고 생각해도 상관 없습니다.
티켓에 적혀있는 번호와 같은 나들목으로 나갈 수 있다면 정렬해서 하나씩 매칭해주는 쉬운 문제입니다. 하지만 이 문제에서는 티켓에 적혀있는 번호와 다른 나들목으로 나가야만 합니다.
이럴 때는 앞뒤 하나씩만 더 봐주면서 DP를 해주면 됩니다. 앞뒤 하나씩, 총 3개를 보면 그 중 하나는 같은 번호의 나들목으로 안 나가기 때문에 문제를 풀 수 있습니다.
전체 코드
1 |
|