문제
수학과 프로그래밍을 좋아하는 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 개의 테스트 케이스가 주어진다. (1≤T≤20) 각 테스트 케이스의 첫 줄에는 두 정수 A,B(1≤A,B<30,000)이 주어지는데, 이는 각각 A와 B가 고른 수를 나타낸다.
- 점수 : 최대 10회 제출하여 취득한 각각의 점수 중에서 최대 점수 (만점 100점) 모든 테스트 케이스를 맞추었을 때 만점을 받는다.
출력
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며, 각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다. 그 다음 줄에, 이 테스트 케이스에서 A가 이기면 1, B가 이기면 2, 무승부이면 3을 출력하여라.
import java.util.ArrayList;
import java.util.Scanner;
class Solution {
static int answerA, answerB, answer;
static boolean[] isPrime = new boolean[30000];
static void check() {
// 소수인지 isPrime에 저장하는 함수
isPrime[2] = true; isPrime[3] = true;
for (int i = 4; i < 30000; i++) {
for (int j = 2; j*j <= i; j++) {
if (i % j == 0) {
isPrime[i] = false;
break;
} else isPrime[i] = true;
}
}
}
static int toInt(ArrayList<Integer> list) {
int num = 0;
for(int i=0; i<list.size(); i++) {
num += list.get(i)*(int)Math.pow(10, list.size()-i-1);
}
return num;
}
static int solve(int n, ArrayList<Integer> arr, int cnt) {
for(int i=0; i<n; i++) {
ArrayList<Integer> temp = (ArrayList<Integer>) arr.clone();
temp.remove(i);
if(isPrime[toInt(temp)]) cnt++;
else {
if(answer < cnt) answer = cnt;
continue;
}
if(temp.size() == 1) {
if(answer < cnt) answer = cnt;
cnt--; continue;
}
else {
solve(temp.size(), temp, cnt);
cnt = 1;
}
}
return answer;
}
public static void main(String args[]) throws Exception {
Scanner sc = new Scanner(System.in);
check();
int T = sc.nextInt();
for(int test_case = 0; test_case < T; test_case++) {
String A = sc.next();
String B = sc.next();
ArrayList<Integer> a = new ArrayList<Integer>();
ArrayList<Integer> b = new ArrayList<Integer>();
for(int i=0; i<A.length(); i++) a.add(A.charAt(i)-'0');
for(int i=0; i<B.length(); i++) b.add(B.charAt(i)-'0');
answer = 0;
if(!isPrime[toInt(a)]) answerA = 0;
else answerA = solve(a.size(), a, 1);
answer = 0;
if(!isPrime[toInt(b)]) answerB = 0;
else answerB = solve(b.size(), b, 1);
System.out.println("Case #"+(test_case+1));
if(answerA == answerB) System.out.println("3");
else if(answerA > answerB) System.out.println("1");
else System.out.println("2");
}
}
}
코드 설명
입력 값을 string형식으로 받아서 자리마다 쪼개 리스트에 넣어준다.
그리고 A와 B 모두 소수인 경우에 solve함수에 넣는데(소수 아닐 시 answer = 0) solve를 재귀 함수로 만들어서 리스트의 길이가 1이 될 때까지 for문을 돌아서 answer값을 갱신해준다.
미리 저장해둔 소수인지 boolean형식으로 저장되어 있는 isPrime과 리스트의 값들을 int로 변환한 값을 비교해서 소수인 경우에만 count를 해준다.
마지막엔 A와 B의 answer값을 비교해서 A 승리시 1, B 승리시 2, 무승부일때 3을 출력해준다.