글 읽기 - 유클리드 게임 질문..

nivea50 7년 전 0

문제에서 말한 최적의 방법이 유클리드 호제법을 말하는 것아닌가요?

20줄의 while문이 몇번 도는지 카운트 한후

카운트 값이 홀수이면 A가 이긴 것이고 짝수이면 B가 이긴 것으로 하였는데 틀렸다고 나옵니다.

반례라도 알 수 있을까요...

#include <stdio.h>

int main(){
	
	
	while(1){
	
		long long a, b, temp, cnt=0;
		scanf("%lld %lld", &a, &b);
	
		if(a==0&&b==0)
			break;
	
		if(a<b){
			temp = a;
			a = b;
			b = temp;
		}

		while(b){
			temp = a%b;
			a = b;
			b = temp;
			cnt++;
		}
	
		(cnt%2>0) ? printf("A wins\n") : printf("B wins\n");
	}	
	return 0;
	
}

음... 예를 들어 31, 13이 남은 상황을 생각해봐요. 31 = 13 * 2 + 5니까 유클리드 호제법대로 하면 13, 5가 되어요. 13, 5를 만들어주는 게 이기는 상황인지 지는 상황인지는 잘 모르겠지만 아마 따져보면 둘 중 하나로 정해지겠죠? 만약에 13, 5를 만들어주면 이긴다고 하면 그렇게 하면 되는데 13, 5를 만들어주면 지는 거면 굳이 13, 5를 만들지 말고 13을 한번만 빼서 18, 13을 만드는거여요. 그러면 다음 번 사람이 무조건 13, 5를 만들고 지게 되겠죠.

잡설은 집어치우고 반례로 5, 2같은 게 있겠어요.

5, 2 -(A)> 3, 2 -(B)> 2, 1 -(A)> 1, 0

이런 느낌으로요.

nivea50 7년 전 0

저는 최적의 방법이 게임의 최소 턴수라고 생각했는데 그게 아니였네요...

문제의 예제에서도 동혁이가 (25,7)->(7,4)이 아닌 (25,7)->(11,7) 준 이유를 알겠네요... (7,4)를 주면 자기가 질걸 아니까!!!!

플레이어라면 자기가 질 패를 상대방에게 주진 않겠지요.. 게임은 이기려고 하는건데!!

그래서 플레이어 입장에서 생각해봤어요.. 자기가 어떤 패를 주면 질것인지...!!!

만약 플레이어가 (a,b)를 계산해서 (b,a%b)를 줄 경우 b가 a%b의 배수이면 상대방이 무조건 이기고

b를 a%b로 나눈 나머지가 (a%b)-1과 같을 경우에도 상대방이 무조건 이긴다는 생각이 들어 이런 경우에는

(a%b)+b, b)를 주도록 하였습니다.. 이걸 주려면 a/b>1을 만족해야겟지용...

이 논리로 코드를 수정했는데.. 사실 짜면서.. 이건 틀렸다는 생각이 강하게 들었어요... 그래도 혹시나.. 혹시나!!! 하는 마음에

제출 해봤는데..역시 틀렸다고 나오네요.. 아아아 모르겠습니다.. 정말 정말... 생각하면 할수록 혼란스럽네요..

무엇을 잘못생각한걸까요 ㅠㅠ... 무지한 저에게 깨달음을 부탁드립니다..ㅠㅠ

#include <stdio.h>

int main(){
	
	while(1){
	
		long long a, b, temp, cnt=0;
		scanf(" %lld %lld", &a, &b);
	
		if(a==0&&b==0)
			break;
	
		if(a<b){
			temp = a;
			a = b;
			b = temp;
		}
		while(a%b){
			cnt++;
			if(a/b>1&&(b%(a%b)==0 ||b%(a%b)==(a%b)-1))
				a = (a%b) +b;
			else{
					temp = a%b;
					a = b;
					b = temp;
				}
				
			printf("%lld %lld\n", a, b);
		}
	
		(cnt%2>0) ? printf("B wins\n") : printf("A wins\n");
	}	
	return 0;
	
}

sait2000 7년 전 3

아까 제가 쓴 댓글 같은 상황을 보면 게임의 상황을 대략 3종류로 나눌 필요성이 있을 것 같아요. 두 수를 a, b (a > b)라 하면
1. a % b == 0일 때: 고민할 필요 없죠? a를 0 만들고 이기면 되겠죠.
2. a % b != 0일 때:
2.1 a / b >= 2일 때: 여기서 중요한 건 이 상황에서 상대방에게 b, a%b라는 상황을 만들어 줄 것인지 만들게 할 것인지 선택할 수 있단 거여요. 즉, b, a%b가 이기든 지든 무조건 이겨요.
2.2 a / b < 2일 때: 할 수 있는 게 하나 밖에 없으니까(그러니까 b, a - b) 그거 하고 나서 남은 상황이 지는지 이기는지 따져봐야겠죠.
근데 이거 이렇게 다 써놔도 되는 걸까요;;

nivea50 7년 전 0

아아아~!~! 감사합니다... 덕분에 3일만에 풀었네요... 2.1이 결정적이네요!! 정말 도움 많이 되었습니다.

그저 감사하다는 말밖에 할말이 없네요. ㄳㄳㄳ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

유클리드 게임 질문..

nivea50 7년 전 0

sait2000 7년 전 2

nivea50 7년 전 0

sait2000 7년 전 3

nivea50 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말