Guest User

Untitled

a guest
Jan 18th, 2019
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.88 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3. char dp[101][101]; //n,m이 주어졌을때 첫 번째 사람이 이기면 1 지면 -1(두 번째 사람이 이기는 경우)
  4. int go(int n, int m){//n,m이 주어졌을때 지금하는 사람이 이길지 질지
  5. if (dp[n][m]) return dp[n][m]; //메모이제이션
  6. if (n == 2 || m == 2) //성공 조건
  7. return dp[n][m] = 1;
  8. if (n > 1){
  9. for (int i = 1; i < n; i++){ //나누었을때 다음사람이 했을 때 지면
  10. if (go(n-i, i) == -1) return dp[n][m] = 1; //이길 수 있다.
  11. }
  12. }
  13. if (m>1){
  14. for (int i = 1; i < m; i++){// 나누었을 때 다음사람이 했을 때 지면
  15. if (go(i, m - i) == -1) return dp[n][m] = 1; //이길 수 있다.
  16. }
  17. }
  18. return dp[n][m] = -1; //여기까지 오면 이기는 경우는 없다 ㅂ2
  19. }
  20. int main(){
  21.  
  22. int n, m;
  23. scanf("%d %d", &n, &m);
  24. if (go(n, m)==1) printf("A\n");
  25. else printf("B\n");
  26.  
  27. return 0;
  28. }
Add Comment
Please, Sign In to add comment