[백준] 1242 소풍

1242번: 소풍

문제 요약

3 6 9 게임과 비슷하게 숫자를 돌리면서

k번째 숫자 마다 지목당한 사람을 제외시킨다.

처음 m번째 있던 사람이 몇번째에 제외되는지를 출력한다.

 

풀이 아이디어

 

직관적인 문제이긴 하나 n이 500만 임으로 단순 구현으로 풀기에는 O(N^2)이 소모된다.

따라서 수학식을 통해 연산량을 줄이는 방법을 채택했다.

 

또한 처음 시작 지점을 

임의로 조정하여

k > m 일때 시작 지점  =  -m

k <= m 일때 시작 지점 =  n-m  로 만들면

 

동호가 항상 남아있는 사람들 중 가장 끝자리에 있겠끔 만들 수 있다.

 

(끝자리로 남길 경우 한 싸이클 계산이 편해진다. )

 

 

3가지 조건을 만들어서

 

k를 추가해도 m 보다 작을 때

- 나누기 연산으로 제외할 수 있는 인원만큼 결과값 추가

- 추가한 인원 만큼 전체 인원 수 제거

- 시작 지점 갱신

+ 만약 추가했을 때 m이 될 경우 탈출

 

k가 지나고 m일 때

- 결과 값에 1 추가 후 반복문 탈출

 

k가 지나고 m을 초과했을 때 (한 싸이클 지남)

- 결과 값에 1 추가 후 인원 수 1 제거

- m 값을 인원 수 n으로 동기화

- 모듈러 연산으로 시작 지점 갱신

 

의 논리로 해결 했다.

 

시행 착오

예시 데이터케이스가 많았기 때문에 한번에 풀렸다.

 

최적화 하기

O(N)에 풀었지만 굉장히 직관적인 문제라서 O(1)이 존재할 것 같아 보인다.

다만 다른 사람들도 O(N)으로 푼 것 같았다.