이 문제는 UNIST 대회인 Uni-CODE 2022의 B번 문제이다. 대회 때 완벽하게 풀어 낸 유일한 문제이다. A번은 어떻게 푸는지 감도 못 잡겠더라. 정해가 빨리 공개되면 좋겠다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 외계인 윤이는 지구를 정복하고자 세계의 중심 도시인 울산을 침략했다. 울산에는 N개의 빌딩이 일렬로 늘어서 있고, 왼쪽에서 i번째 건물의 높이는 \(h_i\)이다. 윤이는 울산을 파괴하기 위해 다음과 같은 계획을 세웠다. 윤이는 매일 UFO를 타고 울산의 상공을 가르며 가장 높이가 높은 빌딩에 레이저를 발사할 것이다. 레이저에 맞은 빌딩은 높이가 1 낮아진다. 만약 그 날에 가장 높이가 높은 빌딩이 여러 개라면, 해당하는 모든 빌딩에 레이저를 발사한다. 만약 이미 모든 빌딩의 ..

상당히 코딩을 늦게 시작한 편이다. 그래서 자료구조의 자 자도 모르는 상태에서 오늘까지 이르렀다. 오늘이 정확히 16일차고, 그 동안 큐(Queue), 스택(Stack), 덱(Deque) 등의 자료구조를 어떻게 사용하는지 알았다. 힙(Heap)도 오늘 배웠는데, 아직 체화시키기에는 조금 모자라서 오늘은 덱을 사용하는 요세푸스 문제를 풀겠다. 사실 큐랑 스택을 하나로 묶어서 덱으로 쓰는 게 가장 편하더라. 덱은 큐와 스택을 한 번에 사용 가능하니 말이다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 ..

어제 출제된 2022 아주대학교 프로그래밍 경시대회 APC A번 문제였다. 다행히 A번이 가장 쉬운 난이도를 가진 문제라서 풀었지, 아니었으면 A번 문제에서 막혔다가 튕겨져 나갈 뻔 했다. 네 번 도전해서 겨우 통과했는데, 할 수 있는 모든 에러를 한 번씩 다 저질러 본 느낌이다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 선우는 APC 문제를 만들기 위해 고민하며 역대 APC들을 둘러보던 와중, 이 대회들의 문제가 난이도가 쉬운 순으로 배치되어 있는 경향을 발견했다! 문제 출제가 완료되고 올해도 이러한 기조를 지키려고 한 선우는 출제하기로 한 문제들에 예상 난이도를 매겨놓았다. 난이도는 브론즈 티어, 실버 티어, 골드 티어, 플래티넘 티어, 다이아몬드 티어 순으로 어려워지며, 동일 난이도가 없도록 엄밀..