무턱대고 풀었다간 $O(N^2)$ 시간복잡도로 TLE된다.
상대적인 위치로 문제를 해결한다.
문제에서 주어진대로 N = 5, M = 2, K = 3을 예로 든다.
T는 게임에서 진행되는 단계이다. 2번째 사람마다 죽으므로 처음엔 2가 죽는다.
우리가 죽이고자(?)하는 사람은 3번째 사람이다. 그러므로 3에대한 번호를 상대적인 위치로 저장하면서 언제죽는지만 체크하면 답을 구할 수 있다.
여기서 단계가 진행될때 마다 전체 인원수($N'$)가 줄어들므로 $N'$이 $M$보다 작아질 경우를 생각해야한다.
#include <cstdio>
int N, M, K;
int main(){
scanf("%d%d%d", &N, &M, &K);
int n;
for (n = 1; n <= N; n++){ //이 안에 답이 나옴
int nM = M % (N - n + 1) == 0 ? N - n + 1 : M % (N - n + 1);
if (K == nM || n == N)
break;
else
K = K > nM ? K - nM : N - n + K - nM + 1;
}
printf("%d\n", n);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기