Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 클레버 타키온
- SWEA
- j7-c
- FILCO
- QC3.0
- USB 테스터기
- MFI
- Code Jam 2019
- 샤오미
- Netmate
- Code Jam
- 퀵차지3.0
- 보조배터리
- Google My Maps
- 유무선 키보드
- NM-LA03
- PLM02ZM
- Full Search
- JP-Q30
- 블루윈
- 프로세서 연결하기
- 이거샀음
- 바이퍼럭스
- cmpt-prog
- 마제스터치 컨버터블2
- 미 파워뱅크
- git-merge
- PLM05ZM
- Dat Bae
- 라이트닝 젠더
Archives
- Today
- Total
이륙하라
SW Expert Academy 5648 "원자 소멸 시뮬레이션" 본문
방법1
전체 원자들을 감싸는 enclosing box의 max(가로, 세로)
초 동안의 모든 움직임을 추적한다.
원자가 중간에 enclosing box의 밖으로 나가면 소멸처리.
같은 시각에 같은 지점에 2개 이상의 원자가 모이는 것이 검출되면 방출 에너지를 구해 답에 누적한다.
괜찮은 구현인 줄 알았는데 제한시간에 아슬아슬하게 걸침. 각 시각마다 정렬하는 것 때문일까?
좌표의 최대 범위를 W라 하면 시간복잡도는 O(W * N * lg N)
방법2
각 원자에 대해 그 원자와 충돌할 수 있는 원자가 있을 수 있는 위치를 미리 검사.
가까이 있는 원자와 먼저 충돌하기 때문에 충돌 소요시간이 작은 것부터 검사한다. 이 문제에선 원자가 상하좌우로만 움직이므로 최대 3개의 위치만 보면 됨. 근데 1.7초나 걸렸나 상수가 큰가보다.
시간복잡도는 O(W * N)
방법3: 더 빠른 사람들의 코드
방법2에서 더 발전한 방법. 위에서 좁은 범위부터 검사한다고 했는데 방법2의 시간복잡도 중 W는 여기서 나온 것이다. 가정할 충돌 소요시간을 1씩 증가시켜가며 검사하기 때문에 불필요한 값에 대해서도 검사한다.
방법3는 모든 충돌 가능성이 있는 모든 원자쌍 사이의 충돌 소요시간, 그 원자쌍의 정보의 리스트를 만들어 충돌 소요시간이 작은 것부터 정렬을 한다. 이렇게 하면 반드시 존재하는 충돌 소요시간에 대해서만 보게 된다.
시간복잡도는 O(N^2)
'WA! PS!' 카테고리의 다른 글
BOJ-11975 Build Gates (1) | 2019.08.04 |
---|---|
SW Expert Academy 1767 "프로세서 연결하기" (0) | 2019.04.12 |
Code Jam 2019 Qualification Round "Dat Bae" (0) | 2019.04.08 |
Comments