반응형
요세푸스 문제
-
BOJ) 요세푸스 문제알고리즘/백준 2020. 6. 25. 17:14
요세푸스 문제 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 풀이 쉽게 봤던 문제였는데, 푸는데 약간의 시간이 들었다. 이미 테이블에서 빼낸 사람을 건너 뛰면서 k번 째 사람을 빼내야 하는 문제에서, 여러 명이 빠져있는 경우에 새롭게 빼내야하는 사람을 어떻게 구해야하는지 생각하는데 시간이 조금 걸렸다. 그래서 결국, k번 째 까지 갈 때, 이미 빠져있는 사람이 있으면 총 가야하는 횟수에 +1을 증가시키면서 자리를 탐색했다. 맞기는 했지만, 배열을 이용해서 하니까 탐색 시간이 너무 많이 걸렸다. 그래서 List로 바꿔서 풀어보기로 했다. List에서 k번 째 있는 사람을 빼내는 동시에 list에서 제..