이륙하라

방법1 전체 원자들을 감싸는 enclosing box의 max(가로, 세로)초 동안의 모든 움직임을 추적한다. 원자가 중간에 enclosing box의 밖으로 나가면 소멸처리. 같은 시각에 같은 지점에 2개 이상의 원자가 모이는 것이 검출되면 방출 에너지를 구해 답에 누적한다. 괜찮은 구현인 줄 알았는데 제한시간에 아슬아슬하게 걸침. 각 시각마다 정렬하는 것 때문일까? 좌표의 최대 범위를 W라 하면 시간복잡도는 O(W * N * lg N) 방법2 각 원자에 대해 그 원자와 충돌할 수 있는 원자가 있을 수 있는 위치를 미리 검사. 가까이 있는 원자와 먼저 충돌하기 때문에 충돌 소요시간이 작은 것부터 검사한다. 이 문제에선 원자가 상하좌우로만 움직이므로 최대 3개의 위치만 보면 됨. 근데 1.7초나 걸렸나 ..

풀고 나서 구글 검색해보니 대부분 DFS의 leaf가 O(5^N) 이다. 사실 많이 커팅되기 때문에 실제론 많이 적을 듯 하지만. 나는 다르게 접근했다. DFS에 들어가기 전에 전처리를 하나 거치는데 존재 가능한 케이블 연결을 (케이블 좌표, 코어id) 쌍으로 표현하여 집어 넣는다. 이런 쌍들의 개수는 최대 48개지만 DFS 중에 이미 연결된 코어를 기록하기 때문에 깊이는 코어의 개수만큼 간다. 각 DFS 노드마다 최대 2가지 경우다. 케이블을 쓰거나, 안쓰거나. 그래서 leaf는 최대 2^N 이다.

Dat Bae 문제의 풀이를 우연히 떠올리게 되어 F=5 테스트케이스도 맞췄는데 구글에서 제시한 풀이는 내 것과 사뭇 달랐다. 내 풀이는 딱 B