[BOJ/백준] 14429번 : 배스킨라빈스 31 (Java)
📘 백준 14429번 : 배스킨라빈스 31
💡 문제 풀이
부르면 지는 수(마지막 수)를 j
, 한 번에 부를 수 있는 수의 수를 m
이라고 한다.
둘이서 하는 31 게임을 무조건 이기는 방법:
선공을 맡는다.
처음에 필승 숫자의 초항까지 부른다.
필승 숫자의 초항 r = (j - 1) % (m + 1)
그 이후로 (상대방 차례 + 본인 차례) 총 2턴동안 부른 수의 길이(개수)가
(m + 1)
이 되게 부른다.
위의 방법으로 진행했을 때 총 턴의 수는
(초항까지 부르는 턴) + (마지막 수를 부르는 턴) + (중간의 수를 부르는 턴)
으로 나눌 수 있는데 이걸 정리해보면
1 + 1 + (상대방 + 본인 차례의 수) * 2
= 2 + (초항 다음 수부터 마지막 수 앞까지를 (m + 1)로 나눈 값) * 2
= 2 + (j - 1 - r) / (m + 1) * 2
✅ 코드 (Java)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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();
}
}