BOJ 20192 : 순서 섞기
2021. 5. 2. 20:58ㆍPS/Ad-hoc & Constructive
20192번: 순서 섞기
정수가 저장된 크기 N인 배열 A가 있을 때, ‘순서 섞기’ 연산은 아래와 같이 정의된다. 크기가 N인 배열 B를 이용하여, 배열 A의 좌측 끝 또는 우측 끝에 있는 값 중 하나를 차례로 꺼내어 배열 B
www.acmicpc.net
관찰이 조금 까다로운 문제이다.
먼저 문제를 관찰하면
수열을 증감 상태로 나타내면 전환되는 점이 있는데, 이를 순서를 바꿀때 전환되는 점이 한번 섞을때 최대 그 반만큼 감소한다는 거다.
그래서 전환점을 O(N)에 찾으면 된다. 바꾼 횟수는 log2(전환점)으로 계산하면 된다.
djayy035/dj035_PS
코드저장소. Contribute to djayy035/dj035_PS development by creating an account on GitHub.
github.com
'PS > Ad-hoc & Constructive' 카테고리의 다른 글
| BOJ 12935 : 트리와 경로의 길이 2 (0) | 2021.11.16 |
|---|---|
| BOJ 1201 : NMK (0) | 2021.11.16 |
| BOJ 15311 : 약 팔기 (0) | 2021.08.04 |
| BOJ 21061 : Beautiful Permutation (0) | 2021.08.03 |
| BOJ 14864 : 줄서기 (0) | 2021.05.11 |