gusul/김태진

구슬/gusul ¶

링크
두명의 선수가 최선을 다할 때, 누가 해당 경기에서 이기는지에 대한 문제
Dynamic Programming
- 내 1년간의 숙원의 문제를 풀었다. -김태진
문제를 단순화하여, 앞으로 홀수번 시행이 최적인 경우, 지금 하는 사람이 승리하게 된다. 이를 이용하여 n-1번째 시행에서(지는 시점을 첫번째로 하여 거꾸로 올라간다.) n번째로 올 때 모두 홀수인 경우에만 해당 시점의 사람이 지게되는데 (1,3,5번에서 7번으로 갈 수 있는데 1,3,5번의 시행횟수가 모두 홀수개) 하나라도 짝수에서 오는 경우가 있으면 그 경우가 상대방이 무조건 지는 경우이므로 최선이다.
즉, 짝수번째 시행자가 무조건 진다고 본다.(점화식)
n-1번째가 모두 홀수이면 자신의 차례 n번째는 짝수여서 지게된다.
n-1번째에 하나라도 짝수 경우가 있으면 n번째에서 n-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;
}

gusul/김태진 (rev. 1.2)

구슬/gusul ¶