[백준/BOJ] 1242번 소풍

굉장히 간단하면서도 어려웠던문제.

처음에 백터를 이용해서 게임의 순서대로 퇴장당하는 위치를 계산후 없애고 순서에 맞게 배열하는 방식으로 접근했으나 시간초과로 틀렸다. 

 

힌트는 질문검색을 보고 알았는데

굳이 모든 노드(친구들)의 위치를 알고 어떤 노드가 없어질지 체크할 필요없이

현재라운드에서의 동호가 몇번째인지만 체크해서 K와 비교하면 된다는 걸 알게되었다.

매 라운드 마다 퇴장당하는 위치의 번호와 동호의 번호를 구해서 같을 때까지 반복하여 라운드 수를 구했던 문제. 

 

문제를 있는 그대로 구현하는 것이 아니라 요약해서 핵심만 구하면  답은 쉽게 낼 수 있는 문제였다.(거기까지 생각해내는 것이 중요하겠지만.... 나는 못했다ㅜㅜ) 

https://www.acmicpc.net/problem/1242

1242번: 소풍

 

 

 

<코드>

#include<iostream>
#include<algorithm>

using namespace std;

int main(void) {
	int N, K, M;

	cin >> N >> K >> M;
	
	int cnt=0;
	int target;
	if (K%N)target = K%N;
	else target = N;	//target이 0이 될때를 고려
	while (1) {
		cnt++;
		if (target == M) {
			break;
		}
		if (M - target > 0) {
			M -= target;
			N--;
			if(K%N)target = K%N;
			else target = N;
		}
		else {
			M -= target;
			M = N + M;
			N--;
			if (K%N)target = K%N;
			else target = N;
			
		}
	}
	printf("%d\n", cnt);
	return 0;
}