[15600] Boss Battle

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

15600번: Boss Battle

<문제>

게임이론에 가까운 문제, n<4일때에는 폭탄이 전범위를 커버하므로 1개로 충분하다.

n==4일때에는, 폭탄을 한번 던진다. {1, 2, 3, 4}에서 2에 던진다고 생각하면

{1, 2, 3}에 보스가 있던 경우에는 커버가 가능하다.

2에 던진 후, 4에 폭탄을 던지면 보스가 {3, 4, 1} 어디에 있더라도 승리가 가능하다.

n==5, {1, 2, 3, 4, 5}에서 2에 던진다면 마찬가지로 3가지 경우가 커버가 가능하다.

보스는 {4, 5}에 존재할때, {3, 4, 5, 1}에 존재할 수 있으므로(정확히는 {3,4,5}와 {4,5,1} ) 2개로 커버가 가능하다.

 

첫 폭탄은 경우의 수를 3개를 줄이고, 이후에는 경우의수를 하나씩밖에 줄이지 못한다. 그렇기에 n<4일때에는 1

n>=4일때에는 n-2가 필요한 최소 폭탄의 개수가 된다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n;
int main(void) {
    cin >> n;
    if (n < 4)
        cout << 1;
    else
        cout << n - 2;
    return 0;
}