이륙하라

울타리 선분을 겹치지 않는다는 조건이 있으면 (세워야 하는 최소 울타리문 개수) = (나뉘어진 영역의 개수) - 1 예를 들면 사각형 모양 울타리 하나만 있으면 바깥 영역, 안쪽 영역으로 2개의 영역이 있고 문은 1개가 필요함 울타리를 만드는 와중에 이미 갔던 곳을 또 간다 == 영역의 개수가 하나 늘어났다 중복 방문하는 "점"이 얼마나 있는지만 세면 된다 방문한 좌표를 1차원 정수로 인코딩해서 배열에 넣고 정렬하면 쉬움 실제 문제 울타리 선분이 겹치는 경우를 생각해야 한다 "안 겹치는 조건에서의 풀이"를 쓰게 되면 겹치는 울타리 선분이 하나 늘어날 때마다 답보다 1만큼 커짐 따라서 중복된 울타리 선분의 개수를 세줘서 빼주면 된다 울타리 선분의 종류를 한 좌표당 N->S, W->E이 두 가지 경우로 생각..

방법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