https://www.acmicpc.net/problem/9655
[필자 사고]
홀 수 짝수 개념으로 해도 문제는 풀린다.
다만 DP공부중이기 때문에 dp적 사고로 풀어야 겠다.
문제에서 주어진 조건은 1과 3
즉 점화식을 구해보면 현재 DP = 과거(DP1) 과 과거(DP3) +1 을 해서 flag 형태로 풀게되면 문제는 풀린다.
[코드 해설]
1. 문제 개요
이 문제는 돌을 1개 또는 3개 가져갈 수 있는 돌 게임에서 마지막 돌을 가져가는 사람이 승리하는 게임입니다.
- 상근(SK)과 창영(CY)이 번갈아 가며 돌을 가져갑니다.
- N개의 돌이 있을 때, 누가 이기는지를 출력하는 문제입니다.
2. 입력 처리 및 초기 조건
- N을 입력받습니다.
- dp 배열을 선언하여, dp[i]는 i개의 돌이 있을 때 최소 턴 수를 저장합니다.
- 초기 값:
- dp[0] = 0 (게임 시작 전)
- dp[1] = 1 (1개 남으면 바로 가져감 → 1턴)
- dp[2] = 2 (1개 + 1개로 가져가야 함 → 2턴)
3. DP 점화식 및 계산
- dp[i] = min(dp[i - 1] + 1, dp[i - 3] + 1);
- 돌을 가져갈 수 있는 방법:
- dp[i - 1] + 1: 1개 가져간 경우 (i-1까지의 최소 턴 + 1)
- dp[i - 3] + 1: 3개 가져간 경우 (i-3까지의 최소 턴 + 1)
- 두 경우 중 더 작은 턴 수를 선택하여 dp[i]를 갱신합니다.
- 돌을 가져갈 수 있는 방법:
4. 승자 판별
- dp[N]이 홀수이면 SK 승리
- dp[N]이 짝수이면 CY 승리
[소스 코드]
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int N;
int dp[1000];
cin >> N;
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= N; i++) {
dp[i] = min(dp[i - 1] + 1, dp[i - 3] + 1);
}
if (dp[N] % 2 == 1)cout << "SK";
else cout << "CY";
}
'백준 > 동적프로그래밍' 카테고리의 다른 글
백준 9507 c++ "Generations of Tribbles" -PlusUltraCode- (0) | 2025.02.09 |
---|---|
백준 14916 c++ "거스름돈" -PlusUltraCode- (0) | 2025.02.07 |
백준 9465 c++ "스티커" -PlusUltraCode- (0) | 2025.02.06 |
백준 1562 c++ "계단 수" -PlusUltraCode- (0) | 2024.12.26 |
백준 c++ 1904 "01타일" -PlusUltraCode- (0) | 2024.05.10 |