A. 게임
두 명의 플레이어가 번갈아가며 숫자를 제거하는 게임을 한다. 초기에 보드 위에 n개의 정수가 존재하며, 각 턴마다 한 명의 플레이어가 하나의 수를 지운다. 이 과정은 보드에 하나의 수만 남을 때까지 반복된다. 선공은 첫 번째 턴을 맡으며, 이후 턴은 플레이어가 번갈아 진행한다.
선공은 최종 남는 수를 최소화하고자 하며, 후공은 이를 최대화하려 한다. 두 플레이어가 최적 전략을 사용할 경우, 마지막에 남는 수는 무엇인가?
입력
- 첫째 줄: 정수 n (1 ≤ n ≤ 1000)
- 둘째 줄: n개의 정수 a₁, a₂, ..., aₙ (1 ≤ aᵢ ≤ 10⁶)
출력
최종적으로 남는 수를 출력한다.
예제
입력:
3
2 1 3
출력:
2
설명
선공이 3을 지우고, 후공이 1을 지울 경우, 2가 남는다. 따라서 결과는 2이다.
풀이
최적 전략을 따르면, 선공은 큰 수를 먼저 제거하고, 후공은 작은 수를 제거하게 된다. 결국 남는 수는 정렬된 배열에서 중간 위치의 값이 된다. 즉, 정렬 후 n이 홀수면 중앙값, 짝수면 중앙 왼쪽 값을 반환하면 된다.
#include <bits/stdc++.h>
using namespace std;
int n;
long long arr[1007];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i)
cin >> arr[i];
sort(arr, arr + n);
if (n % 2 == 1)
cout << arr[n / 2] << '\n';
else
cout << arr[(n - 1) / 2] << '\n';
return 0;
}
B. 마인스위퍼
마인스위퍼 필드는 n×m 크기의 격자로 구성되며, 각 칸은 다음 중 하나일 수 있다: 빈 칸('.'), 폭탄('\*'), 또는 1~8 사이의 숫자.
필드가 유효한지 판단해야 한다. 조건은 다음과 같다:
- 숫자 k가 있는 칸은 주변 8칸 중 정확히 k개의 폭탄을 포함해야 한다.
- 빈 칸('.')은 주변 모든 칸에 폭탄이 없어야 한다.
입력
- 첫째 줄: n, m (1 ≤ n, m ≤ 100)
- 다음 n줄: 각 줄에 m개의 문자열 (., \*, 또는 1~8)
출력
필드가 유효하면 "YES", 아니면 "NO"를 출력한다.
예제
입력:
3 3
111
1*1
111
출력:
YES
풀이
모든 빈 칸에 대해 주변의 폭탄 개수를 세고, 그 결과와 실제 숫자가 일치하는지 확인한다. 만약 빈 칸에 숫자가 있거나, 숫자 칸에 폭탄이 아닌 경우가 있으면 무효.
#include <bits/stdc++.h>
using namespace std;
int n, m;
char grid[105][105];
int bombCount[105][105];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; ++i)
cin >> grid[i];
// 주변 폭탄 수 계산
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == '*') continue;
int cnt = 0;
for (int di = -1; di <= 1; ++di) {
for (int dj = -1; dj <= 1; ++dj) {
if (di == 0 && dj == 0) continue;
int ni = i + di, nj = j + dj;
if (ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] == '*')
cnt++;
}
}
bombCount[i][j] = cnt;
}
}
bool valid = true;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == '.') {
if (bombCount[i][j] != 0) {
valid = false;
break;
}
} else if (grid[i][j] >= '1' && grid[i][j] <= '8') {
if (bombCount[i][j] != grid[i][j] - '0') {
valid = false;
break;
}
}
}
if (!valid) break;
}
cout << (valid ? "YES" : "NO") << '\n';
return 0;
}
C. 유한 여부 판별
각 쿼리는 세 정수 p, q, b로 구성된다. 이때 분수 p/q가 b진수 표현에서 유한 소수인지 판단해야 한다.
유한 소수란 소수점 아래의 자리수가 유한한 경우를 의미하며, 소수점 아래가 0개일 수도 있다.
입력
- 첫째 줄: 쿼리 수 n (1 ≤ n ≤ 10⁵)
- 다음 n줄: 각 줄에 p, q, b (0 ≤ p ≤ 10¹⁸, 1 ≤ q ≤ 10¹⁸, 2 ≤ b ≤ 10¹⁸)
출력
유한 소수면 "Finite", 그렇지 않으면 "Infinite"를 출력한다.
예제
입력:
2
6 12 10
4 3 10
출력:
Finite
Infinite
풀이
분수 p/q가 b진수에서 유한할 조건은: 분모 q의 모든 소인수들이 b의 소인수 집합에 포함되어야 한다. 이를 위해 q와 b의 최대공약수를 반복적으로 약분하여, 최종적으로 q가 1이 되면 유한, 그렇지 않으면 무한.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
while (n--) {
ll p, q, b;
cin >> p >> q >> b;
// 기약분수로 만들기
ll g = gcd(p, q);
q /= g;
// q와 b의 공약수로 반복 약분
while ((g = gcd(q, b)) != 1) {
while (q % g == 0)
q /= g;
}
cout << (q == 1 ? "Finite" : "Infinite") << '\n';
}
return 0;
}
D. XOR 피라미드
배열 b의 길이가 m일 때, 함수 f(b)는 다음과 같이 정의된다:
f(b) = f(b₁⊕b₂, b₂⊕b₃, ..., bm-1⊕bm)
즉, 인접 원소의 비트 단위 합을 반복적으로 계산하여 최종 하나의 값으로 만든다.
예시: f(1,2,4,8) → f(3,6,12) → f(5,10) → f(15) = 15
입력
- 첫째 줄: 배열 길이 n (1 ≤ n ≤ 5000)
- 둘째 줄: 배열 a의 원소들 (0 ≤ ai ≤ 2³⁰ - 1)
- 셋째 줄: 쿼리 수 q (1 ≤ q ≤ 10⁵)
- 다음 q줄: 각각의 쿼리 l, r (1 ≤ l ≤ r ≤ n)
출력
각 쿼리에 대해, 구간 [l, r] 내에서 가능한 연속 부분 배열에 대해 f의 최댓값을 출력한다.
예제
입력:
3
8 4 1
2
2 3
1 2
출력:
5
12
풀이
이 문제는 동적 프로그래밍을 통해 사전 계산이 가능하다. 각 구간 [i, j]에 대해, 해당 구간의 f 값과 최댓값을 저장해두면, 질의 시 상수 시간에 답을 얻을 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5005;
int n, q;
ll a[MAXN], dp[MAXN][MAXN], maxVal[MAXN][MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
dp[i][i] = a[i];
maxVal[i][i] = a[i];
}
for (int len = 2; len <= n; ++len) {
for (int i = 1; i + len - 1 <= n; ++i) {
int j = i + len - 1;
dp[i][j] = dp[i][j-1] ^ dp[i+1][j];
maxVal[i][j] = max({maxVal[i][j-1], maxVal[i+1][j], dp[i][j]});
}
}
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
cout << maxVal[l][r] << '\n';
}
return 0;
}