문제
[백준] 9655번: 돌 게임
https://www.acmicpc.net/problem/9655
이 문제는 단순히 규칙을 찾아내어 푸는 방법과, DP(다이나믹 프로그래밍)로 푸는 방법 2가지 풀이가 존재한다.
우선 단순 규칙을 활용해 푸는 방법부터 알아보자!
코드 1 - 단순 규칙 활용
#include <iostream>
using namespace std;
int main() {
int N;
cin >> N;
// N이 홀수면 상근이 승, 짝수면 창영이 승
cout << (N % 2 ? "SK" : "CY");
return 0;
}
풀이
- 예제 입력1과 같이 돌이 5개일 때, 상근이부터 시작해 돌을 가져가는 경우의 수를 살펴보자.
- 돌이 5개인 경우,
1 + 1 + 1 + 1 + 1
or1 + 1 + 3
or1 + 3 + 1
or3 + 1 + 1
과 같은 방식으로 돌을 가져갈 수 있으며, 이때 이긴 사람은 상근이다. - 이런 식으로 돌의 개수(
N
)별로 돌을 가져가는 경우의 수를 확인하고, 그때마다 누가 이기는지 판단해보자.
N | 경우의 수 | 이긴 사람 |
1 | 1 | 상근 |
2 | 1 + 1 | 창영 |
3 | 1 + 1 + 1 / 3 | 상근 |
4 | 1 + 1 + 1 + 1 / 1 + 3 / 3 + 1 | 창영 |
5 | 1 + 1 + 1 + 1 + 1 / 1 + 1 + 3 / 1 + 3 + 1 / 3 + 1 + 1 | 상근 |
6 | 1 + ... + 1 / 1 + 1 + 1 + 3 / ... / 3 + 3 | 창영 |
7 | 1 + ... + 1 / 1 + 1 + 1 + 1 + 3 / ... / 3 + 3 + 1 | 상근 |
N = 7
까지 경우의 수를 작성하고나니 규칙이 눈에 들어온다.- 바로 N이 홀수이면 상근이가 이기고, N이 짝수이면 창영이가 이기는 것!
- 따라서, 주어진
N
의 홀/짝 여부만 판별하면 누가 승자인지 손쉽게 알아낼 수 있다.
이렇듯 규칙을 찾아내기만 하면 매우 간단하게 코드로 구현할 수 있는 문제이다.
하지만…… 문제 유형이 DP라고 분류되어 있는 만큼, DP로도 풀이해보도록 하자!
코드 2 - DP
#include <iostream>
using namespace std;
int main() {
int N;
cin >> N;
int dp[1001];
// 1: 상근 승, 0: 창영 승
dp[1] = 1;
dp[2] = 0;
dp[3] = 1;
for (int i = 4; i <= N; i++) {
if (dp[i - 1] == 0 || dp[i - 3] == 0)
dp[i] = 1; // 상근이가 이기는 경우
else
dp[i] = 0; // 창영이가 이기는 경우
}
// dp[N]이 1이면 상근이 승, 홀수면 창영이 승
if (dp[N] == 1)
cout << "SK";
else
cout << "CY";
return 0;
}
풀이
앞선 풀이에서 돌의 개수(N
)에 따라 돌을 가져가는 경우의 수를 보다보면,
승자를 결정짓는 요인에 관해 홀/짝 여부와 더불어 한가지 규칙을 더 알아낼 수 있다.
바로 마지막 차례에 돌을 1개 또는 3개를 가져가는 사람이 승자가 된다는 것이다!
이는 바꿔 말하면 N개의 돌이 주어져있을 때,
N-1번째 또는 N-3번째 돌을 가져가는 사람이 상근이라면 창영이가 이기고,
N-1번째 또는 N-3번째 돌을 가져가는 사람이 창영이라면 상근이가 이긴다는 말과 같다.
이제 이 규칙을 가지고 다음과 같이 dp 배열을 초기화할 수 있다.
dp[1] = 1;
dp[2] = 0;
dp[3] = 1;
돌이 i개 있을 때 dp[i] = 1
는 상근이가 이기는 경우를, dp[i] = 0
은 창영이가 이기는 경우를 의미한다.
이제 앞에서 정리한 규칙을 일반화해 다음과 같이 돌이 N개 있을 때의 승자를 판가름할 수 있다.
for (int i = 4; i <= N; i++) {
if (dp[i - 1] == 0 || dp[i - 3] == 0)
dp[i] = 1; // 상근이가 이기는 경우
else
dp[i] = 0; // 창영이가 이기는 경우
}
dp[i - 1] == 0 || dp[i - 3] == 0
은 돌이 i - 1
개 또는 i - 3
개 남은 상황에서 상근이가 돌을 1개 또는 3개 가져감으로써 승리할 수 있음을 의미한다!
이렇게 돌이 i
개 있을 때 승자를 dp배열에 저장한 후, dp[N]
이 1
이면 “SK”
를, 0
이면 “CY”
를 출력하고 종료한다.
회고
DP 문제를 한 1년만에 푸는 것 같다. 왜인지 모르겠지만 아무리 쉬운 문제여도 DP로 풀려면 어렵게 느껴진다..
아직 익숙하지 않아서겠지..? 결국 많이 풀어보는 수밖에 없는 것 같다 😅
'99클럽 TIL' 카테고리의 다른 글
99클럽 코테 스터디 28일차 TIL + 해시(C++) (0) | 2024.11.25 |
---|---|
99클럽 코테 스터디 27일차 TIL + 기타(C++) (0) | 2024.11.24 |
99클럽 코테 스터디 25일차 TIL + 힙(C++) (0) | 2024.11.21 |
99클럽 코테 스터디 24일차 TIL + 힙(C++) (0) | 2024.11.20 |
99클럽 코테 스터디 23일차 TIL + 이차원 벡터(C++) (0) | 2024.11.19 |