주석을 보니 각 집합에 속하는 정점의 개수가 1 2 3 ... N/2 인 경우로 나누어서 걍 경우를 완전탐색하려고 하셨던 것 같습니다
그렇다면 정점이 V개 있을 경우 이 코드는 연산을 몇 번이나 수행할까요?
단순히 정점을 두 집합으로 나누는데만 C(V, 1) + C(V, 2) + ... + C(V, V/2) 개의 경우가 있을텐데 문제의 조건에 1<=V<=20000 이니 V가 커질수록 아주 많은 연산이 필요하겠군요
실제로 이 코드에
1
10000 1
5 6
정도의 적당히 V가 큰 입력을 넣으면 답이 나오지 않습니다.
chsong91 4년 전 1
자바에 발 담근지 두 달도 안 된 초보입니다.
코딩에 깊이도 없고 개념을 자세히 알지 못하지만 알고리즘이 재미있어 감히 탐색부터 시작하여 풀어내려오다가
이 문제까지 왔습니다.
문제를 풀다가 구상한 바를 구현하는데 성공했지만 첫 번째 시도에서 메모리초과가 뜨더군요
인접리스트와 인접행렬에 대한 개념이 없던 제가 메모리초과를 계기로 인접리스트를 조금 알아보고
인접리스트까지 쓰는데 성공했는데(제가 여태껏 쓰던 boolean[][] 간선 배열이 인접행렬인지도 몰랐습니다...)
그런데 이번에는 시간초과가 나네요...
백준 저지에 제출을 하면서 가장 어려운 게 시간을 관리하는 것 이더라구요
개념과 지식이 많이 부족한 탓이겠지요.
배움에는 거부감이 없습니다. 고수님들이 지적하면 달게 받겠습니다.
공부방향과 자세 등을 조언해주셔도 경청하겠습니다.
부디 코딩꿈나무를 도와주세요!!