Gusul/김태진 - Revision history

imported>jereneal at 04:43, 16 July 2013

2013-07-16T04:43:52Z

← Older revision		Revision as of 04:43, 16 July 2013
Line 59:		Line 59:
	return 0;		return 0;
	}		}
			----
			[[ACM_ICPC/2013년스터디]]

imported>jereneal at 04:43, 16 July 2013

2013-07-16T04:43:32Z

← Older revision		Revision as of 04:43, 16 July 2013
Line 4:		Line 4:
	* Dynamic Programming		* Dynamic Programming
	** 내 1년간의 숙원의 문제를 풀었다. -[[김태진]]		** 내 1년간의 숙원의 문제를 풀었다. -[[김태진]]
			* 문제를 단순화하여, 앞으로 홀수번 시행이 최적인 경우, 지금 하는 사람이 승리하게 된다. 이를 이용하여 n-1번째 시행에서(지는 시점을 첫번째로 하여 거꾸로 올라간다.) n번째로 올 때 모두 홀수인 경우에만 해당 시점의 사람이 지게되는데 (1,3,5번에서 7번으로 갈 수 있는데 1,3,5번의 시행횟수가 모두 홀수개) 하나라도 짝수에서 오는 경우가 있으면 그 경우가 상대방이 무조건 지는 경우이므로 최선이다.

			* 즉, 짝수번째 시행자가 무조건 진다고 본다.(점화식)
			* n-1번째가 모두 홀수이면 자신의 차례 n번째는 짝수여서 지게된다.
			* n-1번째에 하나라도 짝수 경우가 있으면 n번째에서 n-1로 만들 때 짝수로 만들 수 있으므로 이기게된다.
	//		//
	// main.cpp		// main.cpp

imported>jereneal at 04:39, 16 July 2013

2013-07-16T04:39:10Z

New page

== 구슬/gusul ==
* [http://211.229.66.5/30stair/gusul/gusul.php?pname=gusul 링크]
* 두명의 선수가 최선을 다할 때, 누가 해당 경기에서 이기는지에 대한 문제
* Dynamic Programming
** 내 1년간의 숙원의 문제를 풀었다. -[[김태진]]
//
// main.cpp
// gusul
//
// Created by Jereneal Kim on 13. 7. 16..
// Copyright (c) 2013년 __ZeroPage__. All rights reserved.
//

#include <iostream>

int main(int argc, const char * argv[])
{
int arr[501][501]={0};
int k1,k2;
int barr[4];
int tmp;
scanf("%d %d %d",&barr[1],&barr[2],&barr[3]);
for(int i=0;i<=500;i++){
for(int j=0;j<=500;j++){
tmp=0;
for(int k=1;k<=3;k++){
if(i>=barr[k]){
if(arr[i-barr[k]][j]==0&&tmp==0){
tmp = 1;
}
}
}
for(int k=1;k<=3;k++){
if(j>=barr[k]){
if(arr[i][j-barr[k]]==0&&tmp==0){
tmp = 1;
}
}
}
arr[i][j]=tmp;
}
}

for(int T=0;T<5;T++){
scanf("%d %d",&k1,&k2);
if(arr[k1][k2]==1){
printf("A\n");
}else{
printf("B\n");
}
}

return 0;
}