돌 게임 3 (feat. 백준, 9657번)

돌 게임 3
https://www.acmicpc.net/problem/9657

9657번: 돌 게임 3

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N;
    bool arr[1001]{false};
    arr[1] = arr[3] = arr[4] = arr[5] = true;
    cin >> N;
    for(register int i = 6; i <= N; ++i){
        if(!arr[i - 1] || !arr[i - 3] || !arr[i - 4])
            arr[i] = true;
    }
    if(arr[N])
        cout << "SK";
    else
        cout << "CY";
	return 0;
}
// *&)*@*

 

반응형

1. 상근이가 이길 수 있도록 최대한 만들어봅니다.
2. 1일때는 상근이가 돌을 가져갈 수 있습니다. (1,3,4 이동 가능하므로)
3. 2일때는 상근이가 돌을 가져갈 수 없습니다.
4. 3, 4일때는 상근이가 돌을 가져갈 수 있습니다. (1,3,4 이동 가능하므로)
5. 5일때는 상근이가 돌을 가져갈 수 있습니다. (3 이동 가능하므로, 3 1 1)
6. 6일때는 5일때 또는 3일때 또는 2일때 창영이가 돌을 가져갔었다면, 상근이가 돌을 가져갈 수 있습니다. (1,3,4 이동 가능하므로)
7. 위 규칙에 따라 dp 식을 만들어주면 되겠습니다.