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
- cmpt-prog
- SWEA
- Netmate
- 마제스터치 컨버터블2
- 바이퍼럭스
- git-merge
- Code Jam
- 샤오미
- USB 테스터기
- 유무선 키보드
- Full Search
- MFI
- 보조배터리
- Dat Bae
- Code Jam 2019
- FILCO
- QC3.0
- JP-Q30
- 이거샀음
- j7-c
- 퀵차지3.0
- NM-LA03
- 프로세서 연결하기
- 블루윈
- 라이트닝 젠더
- PLM05ZM
- Google My Maps
- 클레버 타키온
- PLM02ZM
- 미 파워뱅크
Archives
- Today
- Total
이륙하라
SW Expert Academy 1767 "프로세서 연결하기" 본문
풀고 나서 구글 검색해보니 대부분 DFS의 leaf가 O(5^N) 이다. 사실 많이 커팅되기 때문에 실제론 많이 적을 듯 하지만.
나는 다르게 접근했다.
DFS에 들어가기 전에 전처리를 하나 거치는데 존재 가능한 케이블 연결을 (케이블 좌표, 코어id) 쌍으로 표현하여 집어 넣는다.
이런 쌍들의 개수는 최대 48개지만 DFS 중에 이미 연결된 코어를 기록하기 때문에 깊이는 코어의 개수만큼 간다. 각 DFS 노드마다 최대 2가지 경우다. 케이블을 쓰거나, 안쓰거나. 그래서 leaf는 최대 2^N 이다.
'WA! PS!' 카테고리의 다른 글
BOJ-11975 Build Gates (1) | 2019.08.04 |
---|---|
SW Expert Academy 5648 "원자 소멸 시뮬레이션" (0) | 2019.04.12 |
Code Jam 2019 Qualification Round "Dat Bae" (0) | 2019.04.08 |
Comments