[Java] 8743. 경재와 대환이의 돌게임

D4-8743. 경재와 대환이의 돌게임

 

문제출저: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW2y9NKqPfkDFATy&categoryId=AW2y9NKqPfkDFATy&categoryType=CODE

SW Expert Academy

문제조건이 Java의 경우 100000개 테스트케이스를 합쳐서 2초, DFS를 이용하면 시간초과가 날 것이다.

시간과 메모리 조건만 잘 읽어도 접근방법을 유추할 수 있었다.

필승법을 먼저 찾아야 해결할 수 있다고 생각하였고

그 필승법은 R과 B의 돌 개수를 무조건 1이하로 만드는 것이다.

 

먼저 만들 수 있는 사람이 승리.

 

import java.util.Scanner;

class Solution {
	public static void main(String args[]) throws Exception {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		for(int test_case = 1; test_case <= T; test_case++) {
			long R = sc.nextLong();
			long B = sc.nextLong();
			
			if (Math.abs(R - B) < 2) {
				System.out.println("#" + test_case + " DH");
			} else {
				System.out.println("#" + test_case + " KJ");
			}
		}
	}
}