문제
철수와 영희는 구슬 게임이 구슬 게임을 하려 한다. 이 구슬 게임의 규칙은 다음과 같다.
- 철수와 영희는 번갈아가며 구슬을 가져간다. 맨 처음에는 철수가 구슬을 가져간다.
- 구슬을 가져갈 때에는, 최소 1개에서 최대 3개까지 구슬을 가져갈 수 있다.
- 가져갈 구슬이 없는 사람이 진다.
예를 들어 5개의 구슬이 있다고 하자. 여기서 철수가 1개의 구슬을 가져가고, 영희가 3개의 구슬을 가져간 후, 철수가 마지막으로 1개의 구슬을 가져갔다고 가정하면 이 게임의 승자는 철수가 된다. 물론, 각자가 어떻게 구슬을 가져가느냐에 따라 승패가 달라질 수 있다. 철수와 영희는 이기기 위해서 최선을 다해서 게임을 플레이 한다. n개의 구슬을 시작으로 게임을 진행한다고 할 때, 철수가 이 게임을 이길 수 있다면 YES, 그렇지 않다면 NO를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 전체 구슬의 개수n 이 주어진다. (0 ≤ n ≤ 1,000,000)
출력
첫째 줄에 철수가 이길 수 있으면 YES, 그렇지 않으면 NO를 출력한다.
예제 입력
3
예제 출력
YES
예제 입력
5
예제 출력
YES
예제 입력
191124
예제 출력
NO
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include<iostream>
using namespace std;
int n;
int arr[1000005] = {0,};
int main() {
cin>>n;
arr[1] = 1;
arr[2] = 1;
arr[3] = 1;
for(int i=4; i<=n; i++){
if(!(arr[i-3]==1&&arr[i-2]==1&&arr[i-1]==1)){
arr[i] = 1;
}else{
arr[i] = 0;
}
}
if(arr[n]==1){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
return 0;
}
|
'[C++] 알고리즘 교육 > 16. 동적계획법1' 카테고리의 다른 글
[알고리즘 16.1.6] 동적계획법 - 직사각형 배치의 경우의 수 (0) | 2019.08.12 |
---|---|
[알고리즘 16.1.5] 동적계획법 - 버튼누르기 (0) | 2019.08.12 |
[알고리즘 16.1.4] 동적계획법 - 합병정렬구현하기 (0) | 2019.08.12 |
[알고리즘 16.1.2] 동적계획법 - 직사각형의합 (0) | 2019.08.12 |
[알고리즘 16.1.1] 동적계획법 - 숫자만들기 (0) | 2019.08.12 |
댓글