[백준] 1519번 부분 문자열 뽑기 게임 자바

문제

 

1519번: 부분 문자열 뽑기 게임

 

 

문제 풀이

 

dp배열을 이용하여 해당 게임 판에 써져 있는 N에서 진 부분 문자열을 빼서 만들 수 있는 모든 수의 승패여부를 확인한다.

dp[x] = 숫자 x에 대해서 패배하는지 승리하는지의 여부 저장 (0:아직 모름/ 패배:-1/ 승리: 승리하기 위한 최소 부분문자열)

dp[N+1]로 잡아서 숫자1부터 N까지 담을 수 있도록 한다. 그리고 N이 일의 자리인 경우 부분 문자열을 고를 수 없으므로 무조건 게임에서 지게된다. 따라서 우선 dp[1] ~ dp[9]까지는 -1을 담아 두고, N값에서 부분 문자열을 뺀 값부터 dp적용을 한다. 예를 들어 dp[10]은 dp[9]가 -1이므로 이길 수 있다.

 

부분 문자열은 이중 for문과 substring함수를 이용하여 추출하고, 해당 숫자로 다시 재귀 호출을 한다. 호출 후 돌아온 dp값이 -1이면 실패이므로 호출 전 숫자는 승리하게 된다. win변수로 이겼을 경우를 저장해두고 num변수를 하나 더 사용해서 이기기 위한 최솟값을 갱신한다. win변수를 사용하는 이유는 진 부분 문자열을 뺀 경우를 모두 다 봤을 때 패배면 dp에 -1을 넣고, 이겼을 경우에 num값을 저장한다. 

 

그리고 새롭게 알게된 것이 있는데 int형을 String형으로 만들때 String.valueOf()함수 대신 그냥 바로 + "" 를 붙여주면 간단하게 String타입으로 변경할 수 있다.

 

 

소스 코드

 

public class b_1519 {
	
	static int[] dp;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();		//게임판의 숫자
		dp = new int[N + 1];		//0:모름, 양수:이김, -1:짐
		
		if(N < 10)
			System.out.println(-1);
		else {
			for(int i = 0; i < 10; i++)
				dp[i] = -1;
			System.out.println( solution(N) );
		}
		
		sc.close();
	}
	
	public static int solution(int n) {
		//승패가 결정된 경우 바로 리턴
		if(dp[n] != 0)
			return dp[n];
		
		int num = Integer.MAX_VALUE;		//이길 수 있는 부분 문자열의 최소값
		boolean win = false;			//승패 여부 저장
		String str = String.valueOf(n);
		
        	//진 부분 문자열 구하기
		for(int i = 1; i < str.length(); i++) {
			for(int j = 0; j <= str.length() - i; j++) {
				int temp = Integer.parseInt(str.substring(j, j + i));
				
				if(temp == 0)
					continue;
				
				if(solution(n-temp) == -1) {
					win = true;
					num = Math.min(num, temp);
				}
			}
		}
		
		if(win == false)
			return dp[n] = -1;
		
		return dp[n] = num;
	}
}