Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- char dp[101][101]; //n,m이 주어졌을때 첫 번째 사람이 이기면 1 지면 -1(두 번째 사람이 이기는 경우)
- int go(int n, int m){//n,m이 주어졌을때 지금하는 사람이 이길지 질지
- if (dp[n][m]) return dp[n][m]; //메모이제이션
- if (n == 2 || m == 2) //성공 조건
- return dp[n][m] = 1;
- if (n > 1){
- for (int i = 1; i < n; i++){ //나누었을때 다음사람이 했을 때 지면
- if (go(n-i, i) == -1) return dp[n][m] = 1; //이길 수 있다.
- }
- }
- if (m>1){
- for (int i = 1; i < m; i++){// 나누었을 때 다음사람이 했을 때 지면
- if (go(i, m - i) == -1) return dp[n][m] = 1; //이길 수 있다.
- }
- }
- return dp[n][m] = -1; //여기까지 오면 이기는 경우는 없다 ㅂ2
- }
- int main(){
- int n, m;
- scanf("%d %d", &n, &m);
- if (go(n, m)==1) printf("A\n");
- else printf("B\n");
- return 0;
- }
Add Comment
Please, Sign In to add comment