일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 보조배터리
- SWEA
- 유무선 키보드
- 클레버 타키온
- PLM05ZM
- cmpt-prog
- Dat Bae
- 미 파워뱅크
- 샤오미
- USB 테스터기
- Code Jam 2019
- Netmate
- 마제스터치 컨버터블2
- 프로세서 연결하기
- 퀵차지3.0
- 바이퍼럭스
- 라이트닝 젠더
- QC3.0
- 블루윈
- Google My Maps
- Code Jam
- MFI
- FILCO
- PLM02ZM
- Full Search
- j7-c
- NM-LA03
- 이거샀음
- JP-Q30
- git-merge
- Today
- Total
목록WA! PS! (4)
이륙하라
울타리 선분을 겹치지 않는다는 조건이 있으면 (세워야 하는 최소 울타리문 개수) = (나뉘어진 영역의 개수) - 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 이다.