[c++] 백준 9655번 돌게임 (동적프로그래밍)

문제

돌 게임은 두 명이서 즐기는 재밌는 게임이다.
탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.
두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)

 

출력

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

 

 

문제풀이

n이 짝수이면 창영이가 이기고 홀수이면 상근이가 이긴다.

#include <iostream>
#include <algorithm>
using namespace std;

int main() { //직관에 의한 풀이
    int n;
    cin >> n;

    if(n%2 == 0) cout << "CY" <<endl;
    else cout << "SK" <<endl;
}

하지만 이 문제는 동적 프로그래밍으로도 풀어봐야 하는 문제이다.
돌의 개수에 대해 게임 횟수를 저장하는 배열을 하나 선언한다. 1개 또는 3개의 돌을 가져갈 수 있기 때문에 돌의 개수에 대해 게임횟수를 구하는 방법은 p[n] = min(p[n-1]+1, p[n-3]+1)의 식으로 구해야한다. p[n]을 구했다면 2로 나눠지면 창영이가 이기고 아니라면 상근이가 이긴다.

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    int pickuprock[1000]; //게임 횟수

    pickuprock[0] = 0;
    pickuprock[1] = 1;
    pickuprock[2] = 2; //1 1 로 집음, i-3계산시 존재하지않는 값 접근방지

    for (int i = 3; i <= n; i++){
        pickuprock[i] = min(pickuprock[i-1]+1, pickuprock[i-3]+1);
    }
    if(pickuprock[n]%2 == 0) cout << "CY" <<endl;
    else cout << "SK" <<endl;
}