백준[1561] 놀이 기구 (Python3)
완전 탐색 매 분마다 놀이 기구들의 남은 시간을 확인한다. 이 경우 N = 2,000,000,000, M = 1, M[0] = 30 인 경우 60,000,000,000번의 연산이 필요해 시간 초과가 발생한다. 완전 탐색 최적화 연산 횟수를 줄이기 위해선 탐색하는 빈도를 줄이는 방향으로 갔다. 관찰 결과 아이들이 M 명 이하로 남았을 때를 보면 된다 생각했다. 그중에서도 모든 아이들이 놀이 기구를 타기 직전의 상황을 보면 더 빠르게 문제를 해결할 수 있다고 생각했다. 이분 탐색 임의의 시간 X에 놀이 기구 A는 a 번을 타고, B는 b 번을 타는 식으로 해서 Z는 z 번을 탄다. 이 a + b + c + ... + z를 더한 뒤 아이들의 전체 수인 N과 대소를 비교한다. 시간 X를 정할 때, 최악의 경우 ..
백준[21278] 호석이 두 마리 치킨 (Python3, bfs)
분석하고 보니 플로이드 문제였지만, 시간 복잡도를 계산해 보니 시간이 충분해서 bfs로 풀었다. bfs로 풀 수 있다 생각한 이유 치킨집의 쌍을 구하면 (1, 100), (2, 100) ... (99, 100)로 약 5,000개의 쌍이 생긴다. 간선이 생길 수 있는 개수도 최대가 약 5000개다. 치킨집으로 정한 두 인덱스를 기준으로 bfs 탐색을 진행하면 최악의 경우에 각각 전체를 탐색해야 하고 이러면 10,000번의 탐색이 진행된다. 각 쌍이 10,000번의 탐색을 수행한다 하면 5,000 * 10,000 = 50,000,000 번의 탐색 즉, 약 0.5초 만에 결과를 낼 수 있단 것을 발견해, bfs로 풀이했다. 코드 더보기 from collections import deque N, M = map(..
