목록2024/09/12 (1)
tlov
2565 - 전깃줄
문제: boj.kr/2565날짜: 09/11 (수)성공여부: X [00:52:17] 전깃줄이 교차하지 않도록 최소의 전깃줄을 제거하고 그 개수를 출력하는 문제이다. 가장 먼저 생각해볼 수 있는 알고리즘은 완전탐색이다. 모든 전깃줄을 1개, 2개, 3개, ..., n개까지 제거하면서 최소의 개수를 구하는 것이다. 전깃줄의 개수가 최대 100개이니까 이 방법은 전깃줄을 고르는데에만 100C1 + 100C2 + 100C3 + ... + 100C100만큼의 시간이 걸린다. 가장 큰 경우의 수인 100C50가 약 1 * 10^29이므로 이 방법은 안된다. 그럼 교차하는 수가 많은 전깃줄 위주로 없애는 방법을 생각할 수 있다. 위의 예제를 가장 많은 전깃줄을 교차하는 순으로 정렬하면, 1 83 94 1... 이러..
알고리즘 문제
2024. 9. 12. 10:40