[BOJ 33871] 서로소 게임
View as PDF
Submit solution
Points:
2
Time limit:
1.0s
Memory limit:
1G
Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text
수민이와 송이는 서로소 게임을 하기로 했다. 서로소 게임의 규칙은 다음과 같다.</p>
- 처음에 칠판에 $1$보다 큰 자연수 $N$이 적혀 있다.
- 수민이랑 송이가 번갈아 가며 아래의 단계를 반복한다.
- 현재 칠판에 적힌 수 $x$보다 작으면서 $x$와 서로소인 $1$이 아닌 수 $y$를 하나 골라 $x$를 지우고 적는다.
- 고를 수 있는 $y$가 존재하지 않을 때 게임에서 지게 된다.
수민이와 송이는 최선을 다해 게임을 진행하고 수민이부터 시작하면 누가 이기게 될지 구해보자.
입력 형식
처음에 적힌 수 $N$이 주어진다. $(2 \leq N \leq 10^{9})$
출력 형식
수민이가 이기면 Soomin, 송이가 이기면 Song이라고 출력한다.
예제 입력 1
2
예제 출력 1
Song
예제 입력 2
5
예제 출력 2
Soomin
Comments