취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 26424번 문제인 Coloring Game이다.
문제는 아래 링크를 확인하자.

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

봇과 존의 행동에 따라 앞으로 칠할 수 있는 칸의 수가 어떻게 변하는지를 살펴보자.

봇은 항상 칠할 수 있는 가장 왼쪽 칸만을 골라 칠하므로 봇의 차례에는 앞으로 칠할 수 있는 칸의 수가 1 또는 2 감소할 수 있다.

존은 칠할 수 있는 곳을 적절하게 골라 칠할 수 있으므로 존의 차례에는 앞으로 칠할 수 있는 칸의 수가 1 또는 2 또는 3 감소할 수 있다.

따라서 만약 칸이 5개 이하로 남을 때까지 봇의 차례에는 앞으로 칠할 수 있는 칸의 수가 항상 2 감소하고 존의 차례에는 항상 3 감소하게끔 두 플레이어가 행동할 수 있다면 이 때 봇이 얻을 수 있는 점수가 최소화될 것이다. 이러한 전략은 항상 존재하는데, 이 방법을 찾는 것은 어렵지 않으므로 이를 찾아보는 것은 읽는이들에게 남긴다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int T, N;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> T;
	for (int t = 1; t <= T; t++) {
		cin >> N;
		cout << "Case #" << t << ": " << (N - 1) / 5 + 1 << '\n';
	}
}