https://www.acmicpc.net/problem/24553
N개의 돌 중에 팰린드롬 수만큼의 돌을 가져갈 수 있으며, 마지막에 모든 돌을 가져가는 사람이 이깁니다.
우선 1 ~ 9는 팰린드롬이므로 무조건 먼저하는 사람이 이깁니다.
N = 10이라면 1 ~ 9개를 가져가더라도 9 ~ 1개는 무조건 남기 때문에 먼저하는 사람이 집니다.
그리고 N = 11 ~ 19는 1 ~ 9를 적절하게 뺀다면 다음 사람에게 10을 넘겨줄 수 있으므로 무조건 이길 수 있습니다.
이런식으로 간다면 10의 배수가 아닐때는 무조건 선공이 이긴다는 것을 알 수 있습니다.
0으로 시작하는 수는 없으므로 10의 배수는 팰린드롬이 올 수 없으므로 다른건 고려하지 않아도 됩니다.
|
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
|
#include <iostream>
using namespace std;
typedef long long ll;
ll N;
void func() {
if (N % 10) cout << "0\n";
else cout << "1\n";
}
void input() {
cin >> N;
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
int tc;
cin >> tc;
while (tc--) {
input();
func();
}
return 0;
}
|
cs |
'algorithm > ad-hoc' 카테고리의 다른 글
| boj 7982 순열 그래프의 연결성 판별 (0) | 2024.08.16 |
|---|---|
| boj 16161 가장 긴 증가하는 팰린드롬 부분수열 (0) | 2024.08.15 |
| boj 14370 전화번호 수수께끼 (Large) (0) | 2024.08.06 |
| boj 21316 스피카 (0) | 2024.08.05 |
| boj 10350 Banks (0) | 2024.07.31 |