problem solving
백준 3358: Tower of coins
finding wangdo
2023. 2. 24. 15:46
https://www.acmicpc.net/problem/3358
3358번: Towers of coins
Asen and Boyan are playing the following game. They choose two different positive integers K and L, and start the game with a tower of N coins. Asen always plays first, Boyan – second, after that – Asen again, then Boyan, and so on. The boy in turn can
www.acmicpc.net
게임이론 문제이면서 DP로 푸는 문제다...
사실상 돌 게임 6이랑 똑같은 문제다.
https://www.acmicpc.net/problem/9660
9660번: 돌 게임 6
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000)
www.acmicpc.net
원리는 쉬우니 코드만 첨부하겠다. C언어다.
|
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
|
#include<stdbool.h>
int main()
{
int k, l, m;
scanf("%d %d %d", &k, &l, &m);
bool dp[1000005];
dp[0] = 0;
for (int i = 1;i < 1000001;i++)
{
bool x = 0;
x = x || !dp[i - 1];
if (i >= k)
x = x || !dp[i - k];
if (i >= l)
x = x || !dp[i - l];
dp[i] = x;
}
for (int i = 0;i < m;i++)
{
int k;
scanf("%d", &k);
printf(dp[k] ? "A" : "B");
}
}
|
cs |