[BOJ] 9657번 : 돌 게임 3

1. problem : 

https://www.acmicpc.net/problem/9657

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
vector<string> winners = { "SK","CY" };
int n; 
vector<int> rocks = { 1,3,4 }; 
int d[1005]; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n; 
	d[1] = 0, d[2] = 1, d[3] = 0, d[4] = 0; 
	for (int i = 5; i <= n; i++) {
		for (auto rock : rocks) {
			if (d[i - rock] == 1) {
				d[i] = 0;
				break;
			}
			else d[i] = 1;
		}
	}
	cout << winners[d[n]];
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/9657.cpp

basic-algo-lecture/0x10/solutions/9657.cpp at master · encrypted-def/basic-algo-lecture

dp를 이용해서 푼다. 따라서, 세 가지 스텝을 따른다. 

1. 테이블을 정의한다. d [i] = i개의 돌일 때, 상근이가 이기면 0, 창영이가 이기면 1 (선공은 상근이) 

2. 점화식을 작성한다. 상근이가 1,3,4개 중 하나를 골랐을 때, 만약 d [i-j]가 1이라면, 즉 , 상근이가 선공했을 때 창영이가 이긴다면 이번에는 창영이가 선공으로 생각할 수 있으므로, 창영이가 진다. 따라서, d [i] = 0가 된다. 상근이가 이겼기 때문에, break 한다. 만약, d [i-j]가 0이라면, 상근이가 선공했을 때 상근이가 이기므로, 창영이가 선공했을 때는 창영이가 이긴다. 따라서, d [i] = 1이 된다. 

3. 초기값을 설정한다. d[1]  = 0, d [2] = 1, d [3] = 0 , d [4] = 0으로 , 4개까지 고를 수 있으므로 d [4]까지 초기값을 설정해 준다. 

나는 테이블을 정의할 때, d[i] = 0 or 1로 두는 생각을 못했다. 상근이와 창영이를 따로 생각했다. 이제부터 이러한 방법도 기억하고 써먹을 것이다.