PS/SCPC

[SCPC - 2019년 2차 예선] 소수 수열 (JAVA)

제이온 (Jayon) 2020. 8. 18.

문제

수학과 프로그래밍을 좋아하는 A와 B 두 사람이 다음과 같은 게임을 하고 있다. 둘은 각각 1 이상 30,000 미만의 수 하나를 고른다.

 

이 수를 가지고 점수를 계산하여 큰 쪽이 이기는 게임이다. 어떤 수의 점수는, 이 수부터 시작해서 한 자리를 골라 이 자리의 숫자를 지워서 소수를 만들고, 이 과정을 연속해서 최대로 많이 만들 수 있는 소수의 개수이다. 이 과정에는 입력받은 원래의 수도 포함된다.

 

예를 들어, 127은 자신이 소수이다. 만약 7을 지우면 12가 되고, 이는 소수가 아니다. 그러나, 7을 지우는 대신 2를 지워서 17, 다시 1을 지워서 7을 만들면 총 3개의 소수를 연속해서 만들 수 있으며, 127의 점수는 3, 즉 127에서 규칙을 지키면서 소수를 최대로 많이 만들 수 있는 경우라는 것을 쉽게 보일 수 있다.

 

어떤 숫자를 지우더라도 소수를 만들 수 없다면 종료한다. A와 B가 제시한 수에서 규칙에 의해 소수의 수열을 만들었을 때, 더 높은 점수를 얻는 수를 제시한 쪽이 이긴다. 둘이 제시한 수의 점수가 같다면 무승부이다.

 

규칙상, 소수가 아닌 수를 낸다면 이 수를 낸 쪽이 지거나, 비기는 경우 두 가지만 가능하다. 예를 들어, 128을 냈다면 이 수는 소수가 아니므로 이 수의 점수는 0점이고, 상대방도 합성수를 낸다면 비기고, 그렇지 않다면 지게 된다.

 

또한, 1은 소수가 아니다. A와 B가 제시하는 수의 어느 자리에도 0이 들어 있지 않다. 즉, 107과 같은 수를 제시할 수 없다. A, B가 고른 두 수를 가지고 승패를 결정하는 프로그램을 작성하시오.

 

 

입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T 가 주어지고,


이후 차례로  T 개의 테스트 케이스가 주어진다. (1T20)(1≤T≤20)
각 테스트 케이스의 첫 줄에는 두 정수 A,B(1A,B<30,000)A,B(1≤A,B<30,000)이 주어지는데, 이는 각각 AA BB가 고른 수를 나타낸다.  



- 점수 : 최대 10회 제출하여 취득한 각각의 점수 중에서 최대 점수 (만점 100점)
모든 테스트 케이스를 맞추었을 때 만점을 받는다.

 

 

출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다.
그 다음 줄에, 이 테스트 케이스에서 A가 이기면 1, B가 이기면 2, 무승부이면 3을 출력하여라. 

 

 

풀이

간단한 수학적인 지식과 다이나믹 프로그래밍으로 풀 수 있는 문제였습니다.

 

점화식을 세우는 부분은 어렵지 않았지만, 문제를 똑바로 읽지 않으면 틀릴 요소가 다분했습니다.

크게 주의할 점은 2가지가 있습니다.

 

전자는 특정 수의 요소를 연속적으로 제거하는 것이지, 띄엄 띄엄 제거할 수 있는 것이 아니었습니다.

후자는 제거하려는 수가 합성수일 경우, 제거 과정을 생략한다는 점이었습니다.

 

저는 전자와 후자 모두에서 삽질을 하는 바람에 무려 10번이나 시도해서 문제를 맞출 수 있었습니다.

이제 서론은 줄이고, 본격적인 풀이 설명을 해 보겠습니다.

 

먼저, 점화식은 아래와 같이 표현할 수 있습니다.

 

 

dp[n] = (isPrime) ? (max(Sn) + 1) : 0

 

 

여기서 Sn은 각 자릿수를 하나씩만 제거한 수들의 집합입니다.

예를 들어, 127에 경우 Sn = {12, 17, 27}가 됩니다.

 

각 자릿수를 하나씩만 제거하는 이유는 간단합니다.

예를 들어, 127 중에 자릿수 하나를 제거한 12에 경우, 미리 dp 배열에 저장되어있을 것이기때문이죠.

따라서, Sn 중 가장 큰 dp 값을 선택하고 거기에 1을 더한 값을 새롭게 dp[n]에 넣어주면 됩니다.

마지막을 1을 더하는 이유는 n이 소수이기때문이죠. 소수가 아니라면, 바로 dp[n] = 0 처리하면 됩니다.

 

위의 과정을 bottom-up 방식으로 구현하시면 됩니다.

 

추가로, A와 B가 제시한 숫자의 수가 최대 29999로, 수가 크지 않으므로 에라토스테네스의 체는 구현하지 않고, 기본적인 소수 판별 알고리즘을 사용하였습니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.

댓글

추천 글