12842번 튀김 소보로

문제 설명

사람들마다 소보로를 먹는 속도가 정해져 있을 경우, 남아있는 소보로의 개수를 보고 마지막으로 소보로를 집어든 사람은 누구인지 찾는 문제입니다.

 

내가 푼 방식

규칙 찾기

사람들이 소보로를 먹는 시간이 정해져 있다. -> 이 정해진 시간을 통해 규칙을 찾아낼 수 있다는 생각이 들었습니다.

 

다음 사진은 문제의 예시를 시간의 흐름에 따라 1번, 2번, 3번 사람이 먹게 될 소보루 번호를 매겨본 것입니다.

(1번은 1초에 한 개, 2번은 3초에 한 개, 3번은 5초에 한 개를 먹을 경우)

규칙

(문제에서 동시에 소보루를 잡는다면 낮은 번호가 먼저 소보로를 집는다고 서술돼 있음)

먹은 소보루 개수가 1개일 경우, 1번이 마지막으로 소보루를 잡은 사람이 된다.

먹은 소보루 개수가 2개일 경우, 1번 다음 2번이 소보루를 잡게 되므로 2번이 마지막 소보루를 잡은 사람이 된다.

먹은 소보루 개수가 3개일 경우, 2번 다음 3번이 소보루를 잡게 되므로 3번이 마지막 소보루를 잡은 사람이 된다.

먹은 소보루 개수가 4개일 경우, 1번이 두 번째 소보루를 먹은 경우이므로 1번이 마지막 소보루를 잡은 사람이 된다.

먹은 소보루 개수가 5개일 경우, 1번이 세 번째 소보루를 먹은 경우이므로 1번이 마지막 소보루를 잡은 사람이 된다.

먹은 소보루 개수가 6개일 경우, 1번이 네 번째 소보루를 먹은 경우이므로 1번이 마지막 소보루를 잡은 사람이 된다.

먹은 소보루 개수가 7개일 경우, 2번이 1번 다음으로 소보루를 잡게 되므로 2번이 마지막 소보루를 잡은 사람이 된다.

...

위의 규칙을 통해 생각해낸 것

1. 초 단위의 규칙이 있다는 것을 인지

이런식으로 이어지게 된다면 각각의 먹는 간격인 1, 3, 5의 최소 공배수인 15초 단위로 먹는 순서의 규칙이 반복된다는 것을 알 수 있습니다.

2. 개수 단위의 규칙이 있다는 것을 인지

0~14초 사이에 23개의 소보루를 먹게 된다 -> 소보루를 먹는 동안 23개 마다 규칙이 반복된다는 생각이 들었습니다.

3. 먹은 소보루 개수를 23으로 나눈 나머지로 마지막으로 소보루를 잡은 사람을 판단할 수 있음을 확인

 

찾은 규칙을 통해 문제 로직 구하기

1. 소보루 먹는 시간의 최소공배수 구하기

2. (최소공배수) / (각각의 사람의 소보루 먹는 시간) 의 합 구하기

3. (먹은 소보루 개수) % (2.에서 구한 합)

4. 소보루 먹는 순서 규칙을 구함

 

제출 1

위의 로직 순서대로 간단한게 코드를 작성해서 제출해봤다.

제출 1

분명 결과 퍼센티지가 90%를 넘었는데도 틀렸습니다가 나왔다... 이 말은 특정 케이스에 대한 로직이 잘 못 됐다는 것이므로 다시 코드를 확인해보았다.

 

제출 2

내가 짠 코드 내에는 순서 3.이 0이 될 경우에 대한 로직이 존재하지 않았다. 그래서 0이 될 경우에 대한 로직을 추가해주니

제출 2

맞았습니다!!!!!

 

 

 

백준 링크 : https://www.acmicpc.net/problem/12842

12842번: 튀김 소보루

GitHub 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/12842.py