백준 1242번 소풍

문제링크: https://www.acmicpc.net/problem/1242

사용한 알고리즘: 수학


사람 수 N 과 찾고자하는 위치 M, 사람을 빼는 순서 K 를 주고, M위치의 사람이 몇번째로 빠져나가는지 구하는 문제였습니다.
펜윅트리를 통해 풀려고 하였으나, 상당히 오랜 시간 풀지 못하여 많은 글들을 찾아보고, lyzqm님의 풀이를 많이 참고하여 풀었습니다.

풀이는 다음과 같습니다.
M번째 사람의 위치를 차례가 흘러감에 따라 상대적으로 저장하면서 언제 빠질 수 있는지만 확인 하면 되는 문제였습니다. 이때 전체 이원수가 변화하는 것을 유의하면서 풀어가야 합니다. 이를 생각하는 것이 굉장히 까다로웠습니다.
풀이만 잘 생각할 수 있다면 구현은 허무할 정도로 짧고 간단한 문제였습니다.