[BOJ/백준] 14429번 : 배스킨라빈스 31 (Java)

📘 백준 14429번 : 배스킨라빈스 31

---

문제 바로가기

💡 문제 풀이

---

부르면 지는 수(마지막 수)를 j, 한 번에 부를 수 있는 수의 수를 m이라고 한다.

둘이서 하는 31 게임을 무조건 이기는 방법:

1. 선공을 맡는다.

2. 처음에 필승 숫자의 초항까지 부른다. 필승 숫자의 초항 r = (j - 1) % (m + 1)

3. 그 이후로 (상대방 차례 + 본인 차례) 총 2턴동안 부른 수의 길이(개수)가 (m + 1)이 되게 부른다.

위의 방법으로 진행했을 때 총 턴의 수는

(초항까지 부르는 턴) + (마지막 수를 부르는 턴) + (중간의 수를 부르는 턴)

으로 나눌 수 있는데 이걸 정리해보면

1 + 1 + (상대방 + 본인 차례의 수) * 2

= 2 + (초항 다음 수부터 마지막 수 앞까지를 (m + 1)로 나눈 값) * 2

= 2 + (j - 1 - r) / (m + 1) * 2

✅ 코드 (Java)

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/14429
// 둘이서 31 게임을 무조건 이기는 방법: 선공을 맡는다.
// 필승 숫자의 초항을 부른다. (j - 1) % (1 + m)
// 그 이후로 (상대방 -> 본인) 턴이 총 (m + 1)이 되게 부른다.
// 이걸 계산하자면 (전체 - 부르면 지는 수를 부르는 턴 - 초항)을 (m + 1)로 나누는데 이게 2명이서 맞춰 부른 턴이기 때문에 2를 곱하고
// 거기에 초항을 부르는 턴과 부르면 지는 수를 부르는 턴을 더하면 최소 턴수로 이길 수 있음.
public class B14429_배스킨라빈스_31 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()); // 플레이할 게임의 판 수
		int minCnt = Integer.MAX_VALUE; // 최소 턴의 수
		int minIdx = 0; // 최소 턴의 게임 번호
		for (int i = 1; i <= n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int j = Integer.parseInt(st.nextToken()); // 말하면 지는 숫자
			int m = Integer.parseInt(st.nextToken()); // 한 턴에 말할 수 있는 최대 자연수의 개수
			int r = (j - 1) % (1 + m); // 필승 숫자의 초항
			int cnt = (j - 1 - r) / (m + 1) * 2 + 2; // 최소 턴 수의 길이
			if (cnt < minCnt) { // 최소 턴 수를 가지는 게임 갱신
				minCnt = cnt;
				minIdx = i;
			}
		}
		System.out.println(minIdx + " " + minCnt); // 출력
		br.close();
	}
}

💾 제출 결과

---

보러 가기

🔗 참고한 자료

---

• 31 게임 이론