https://www.acmicpc.net/problem/25320
문제 요약
- A먼저 시작하고, A와 B가 번갈아서 아래의 작업 수행
- BLOCK : 블록을 새롭게 놓음
- CHAIN : 앞선 블록 위에 블록을 놓는데, 블록 번호가 더 커야함
- 2N개의 블록(2 * 100000)
- BLOCK 기록만 주어졌을때 이게 가능한지? 어떻게 가능한지?
접근법
- 작은 블록부터 CHAIN을 처리하는데 여러가지를 고려한다.
- 큰 흐름과 예외 처리가 필요하다.
큰 흐름
- 블록 번호가 큰 것은 놓기 쉽고, 작은 것은 놓기 어려움 => 이미 놓여진 블록 중 번호가 작은 것에 CHAIN을 이어나가는데 이어 나갈때는 남은 것중 번호가 작은것부터 붙여나감 ==> 22)
- 이미 놓여진 블록 중 같은 것이 연속으로 되어있는 것들이 있으면 꼭 CHAIN을 놓아야함. 이 때도 작은 숫자부터 처리 ==> (1)
- (1)을 처리하고, (2)를 처리한다.
- A, B 사용 가능한 나무 블록 개수
- 사용 가능한 블록 번호
- 구현은 뒤에 적겠음
예외처리
- B 먼저 시작
- 입력에서 중복번호
- 연속 같은 사람 처리가 안됨
- 마지막이 A인경우 처리하라는 의견이 있지만 별도로 하지는 않았음
구현
- 초기 입력을 시작으로 CHIAIN을 이어붙임 => vector
- 초기 입력 예외 확인
- A,B 사용 블록 개수 카운팅
- 처리 1 - CHAIN을 꼭 넣어야하는 처리
- 초기 입력에서 AA, BB 인 경우 모아서 오름차순 정렬
- 사용 가능한 숫자 모아놓고 정렬
- 작은 곳 부터 CHAIN을 붙여나감
- 처리 2 - 작은 숫자부터 개별 처리
- 모든 BLOCK들을 오름차순 정렬
- 사용 가능한 숫자 모아놓고 정렬 <= 처리1 때문에 바뀌었을 것임
- 작은 곳 부터 CHAIN을 붙여나감 <= AB 패턴으로 붙여질 것임
- BLOCK이 끝인 경우는 편하게 이어나감
newbieski