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
- Netmate
- j7-c
- 보조배터리
- 라이트닝 젠더
- 바이퍼럭스
- USB 테스터기
- Code Jam
- Full Search
- QC3.0
- 마제스터치 컨버터블2
- 미 파워뱅크
- PLM02ZM
- 클레버 타키온
- JP-Q30
- Google My Maps
- MFI
- FILCO
- 퀵차지3.0
- 이거샀음
- Dat Bae
- PLM05ZM
- git-merge
- 유무선 키보드
- Code Jam 2019
- NM-LA03
- 샤오미
- 프로세서 연결하기
- 블루윈
- cmpt-prog
- SWEA
Archives
- Today
- Total
이륙하라
BOJ-11975 Build Gates 본문
울타리 선분을 겹치지 않는다는 조건이 있으면
- (세워야 하는 최소 울타리문 개수) = (나뉘어진 영역의 개수) - 1
- 예를 들면 사각형 모양 울타리 하나만 있으면 바깥 영역, 안쪽 영역으로 2개의 영역이 있고 문은 1개가 필요함
- 울타리를 만드는 와중에 이미 갔던 곳을 또 간다 == 영역의 개수가 하나 늘어났다
- 중복 방문하는 "점"이 얼마나 있는지만 세면 된다
- 방문한 좌표를 1차원 정수로 인코딩해서 배열에 넣고 정렬하면 쉬움
실제 문제
- 울타리 선분이 겹치는 경우를 생각해야 한다
- "안 겹치는 조건에서의 풀이"를 쓰게 되면 겹치는 울타리 선분이 하나 늘어날 때마다 답보다 1만큼 커짐
- 따라서 중복된 울타리 선분의 개수를 세줘서 빼주면 된다
- 울타리 선분의 종류를 한 좌표당 N->S, W->E이 두 가지 경우로 생각해서 무방향 울타리 선분을 1차원 정수로 인코딩해서 배열에 넣고 정렬
'WA! PS!' 카테고리의 다른 글
SW Expert Academy 5648 "원자 소멸 시뮬레이션" (0) | 2019.04.12 |
---|---|
SW Expert Academy 1767 "프로세서 연결하기" (0) | 2019.04.12 |
Code Jam 2019 Qualification Round "Dat Bae" (0) | 2019.04.08 |
Comments