문제

어느 대학교의 두 학과 A, B가 함께 MT를 떠났다. A학과에서 MT를 온 학생들은 a명, B학과에서 MT를 온 학생들은 b명이다. 처음 보는 학생들끼리 MT를 왔기 때문에, 친목을 도모하기 위해서 다음과 같은 게임을 하기로 했다. 게임의 규칙은 다음과 같다.

① 총 a+b명의 학생들이 게임에 참가한다. 단, a≥b이다.

② 두 자연수 N,K를 미리 정한다. N은 K보다 작을 수도, 같을 수도, 클 수도 있다. N은 MT 게임이 끝나는 수이고, K는 게임에 참가한 학생(1명)이 연속한 숫자를 부를 수 있는 최대 개수이다.

③ A, B두 학과는 모두 자기 학과에 속한 학생들을 한 줄로 세워서 순서를 정한다.

④ A학과의 첫 번째 학생은 1부터 K까지 중에서 자연수 하나를 마음속으로 정하고, 1부터 시작하여 ‘본인이 마음속으로 정한 수’만큼 연속한 숫자를 말한다.

⑤ A학과의 두 번째 학생도 1부터 K까지 자연수 하나를 마음속으로 정하고, 앞 학생이 마지막으로 부른 숫자 바로 다음 숫자부터 시작하여 ‘본인이 마음속으로 정한 수’만큼 연속한 숫자를 말한다. 마음속으로 수를 정할 때, 이미 다른 학생이 정한 수와 같을 수도 있고 다를 수도 있다.

⑥ 이 과정을 반복하다가, A학과의 마지막 학생이 끝나면 B학과의 첫 번째 학생이 이어서 진행한다. B학과의 학생들도 같은 규칙에 따라 게임을 진행하다가, B학과의 마지막 학생이 끝나면 A학과의 첫 번째 학생이 이어서 진행하고, 이런 과정을 반복한다.

⑦ 이 과정에서, 어떤 학생이 N을 말하게 되면, N을 말한 학생이 속한 학과가 게임에서 지게 된다.

아래 표는 a=3, b=2, N=17, K=3인 경우의 예이다. A학과의 학생들을 차례로 A1,A2,A3라고 하고, B학과의 학생들을 차례로 B1,B2 라고 한다.

두 학과 학생 모두 자기 학과가 지지 않게 하려고 최선을 다한다. 그러나, 두 학과 학생들은 게임을 진행하는 과정에서 이 게임에는 어떤 성질(규칙)이 숨겨져 있다는 것을 알게 되었다. 즉, 두 학과의 학생 수 a,b 와 N,K 값이 주어지고 두 학과의 학생들 모두가 그 성질을 안다면, 두 학과 학생들 모두 지지 않기 위해 최선을 다하더라도 어느 한 학과가 반드시 이긴다는 것이다. 이 게임에서 두 학과의 학생 수 a,b 와 N,K 값이 주어질 때, 반드시 이기는 학과를 구하는 프로그램을 작성하시오. 단, 이 게임은 항상 A학과 학생부터 시작하고, 여러 번 반복해서 게임을 한다고 한다. ( 게임 반복 횟수 c )

입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에는 테스트 케이스 개수를 나타내는 자연수 T가 주어지고, 이후 차례로 T 개의 테스트 케이스가 주어진다. ( 1≤T≤40 ) 각각의 테스트 케이스 첫 줄에는 A학과의 학생수 a , B학과의 학생 수 b , 게임 반복 횟수 c , 이렇게 3개의 자연수가 공백(빈칸)을 사이에 두고 차례로 주어진다. 그 다음 c개의 줄에는 MT 게임에서 사용되는 두 자연수 N,K 가 공백(빈칸)을 사이에 두고 차례로 주어진다. 이 수들의 범위는 1≤b≤a≤10,000, 1≤c≤7, 2≤N≤1,000,000, 1≤K≤1,000 이다.

출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며, 각 테스트 케이스마다 첫 줄에는 “Case #T”를 출력하여야 한다. 이때 T는 테스트 케이스의 번호이다. 그 다음 줄에는 반드시 A학과가 이긴다면 ‘a’를 출력하고, 반드시 B학과가 이긴다면 ‘b’를 출력하되, 만약 “게임 반복 횟수”가 2 이상(2≤c≤7)이라면, 각 게임에서 이기는 학과를 연속해서 출력하라. 즉, 각 테스트 케이스 마다 총 c 번 게임을 하기 때문에 각 테스트 케이스에 대한 출력 결과는 a 또는 b로 구성된 문자열이며, 문자열 길이는 ‘c’이다. 여기서, 출력해야 할 문자 a 와 b는 소문자 임에 주의하라.

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 = 0; test_case < T; test_case++) {
			
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			
			char[] win = new char[c];
			
			for(int i=0; i<c; i++) {
				int N = sc.nextInt();
				int K = sc.nextInt();
				
				if(K==1) {
					N %= a+b;
					if(a >= N && N != 0) win[i] = 'b';
					else win[i] = 'a';
				}
				// n:n
				else if(a==b) {
					N %= a*(K+1);
					if(a >= N && N != 0) win[i] = 'b';
					else win[i] = 'a';
				// n:m (n>m)
				} else {
					if(a >= N) win[i] = 'b';
					else {
						N %= a+b*K;
						if(a >= N && N != 0) win[i] = 'b';
						else win[i] = 'a';
					}
				}
			}
			
			System.out.println("Case #"+(test_case+1));
			System.out.println(win);
		}
	}
}

코드 설명

우선 게임의 필승법은 무조건 두 팀이 한 번씩했을 때 만들 수 있는 숫자가 있다.

N을 그 수로 나누고 그 나머지보다 작은 수를 먼저 시작한 a팀이 말하고 끝난다면 무조건 a->(b->a)->(b->a)->b 이렇게 되므로 b팀이 N번째 수를 말하게 된다.

만약 a팀과 b팀의 수가 같다면 (b->a)의 값으로는 a*(k+1) 가 된다.

하지만 a팀과 b팀의 수가 다르다면 (b->a)의 값으로는 a + bk가 된다. (a>b이므로 a팀의 조절로 저 간격이 만들어 질 수 있다.)

150만점에 127.5점이 나오는데 n:m관계의 if문에 조건이 빠진 것같다………아직 잘 모르겠동

문제출처 : codeground