백준 32714번 방벽게임

백준 32714번 방벽 게임

문제를 보면 가로 또는 세로로 연속하는 두 칸을 선택해서 방벽을 설치할 수 있다고 한다.
쉽게 말해 그냥 방벽을 설치하는 것이다.
세로로도 방벽을 설치할 수 있다.

건덕이가 움직이는 걸 시뮬레이션으로 직접 코딩할 필요가 없다. 위치를 추적하거나 규칙을 확인할 수 없지 않기 때문이다.(다시 생각해보니 위치추적도 시뮬레이션으로 안해도 될 것 같긴 함) 규칙성만 발견하여 움직이는 횟수만 계산하면 된다.

규칙성도 바로 보일 것 같이 생겨서 만만하게 봤는데 만만한 게 맞았다. 한 10분정도 걸렸다. 구구단 문제는 8분 걸렸고, 비슷한 수준의 문제 같다.

그런데 처음에는 지그재그로 막게 하면 될 거라고 생각하고 1+1+(2(k-3)) + 1로 식을 세웠다. 그런데 오답이 나와서 지그재그보다 효율적인 게 있구나 라고 생각했다.

이런 길 건너기 방해하는 문제는 처음 풀어보는데 사실 문제가 반가웠었다. 스타크래프트 성큰 디펜스가 생각났었다. 어렸을 때 이런 맵들을 엄청 좋아 했었고, 시리즈별로 다 해봤었다.

그래서 그런지 아니면 문제가 쉬워서 그런지 정답은 바로 생각이 났다.

건덕이가 아래로 쭉 오니까 다시 왔던 길을 되돌아가도록 만드는게 제일 베스트이다.

맵이 가로로 길쭉한 정사각형이라 하더라도 즉, 가로로 지그재그하더라도

건덕이는 아래로 쭉 오니까 왔던길을 되돌아가도록 만드는게 베스트일 것이다.

스타크래프트에서는 먼저 벽을 다 세우게 하고 유닛이 움직인다.

그래서 저런식으로 벽을 세우면 즉시 최단 루트를 돌아 N=4같은 경우에 즉시 오른쪽 아래 아래로 이동한다. 그런데 여기서는 먼저 벽 세우는 게 아니다. 건덕이가 한 칸 이동하고 건구스가 막고 이렇게 순서대로 게임이 진행된다. 그래서 건덕이가 왔던 길을 되돌아가도록 만들 수 있다. N=4일 때가 확인하기 쉬우니 N=4, N=5일 때로 규칙을 확인해보면, 규칙성을 찾을 수 있다. 자세한 건 사진에 적어놓았다.

사진을 보면 처음에는 단순히 건덕이 옆의 세로를 막으면 된다고 생각하고 계산해서 풀었는데 우연히 답만 맞았고 로직은 틀렸었다.
틀렸다는 제보가 들어와 다시 생각해봤고, 그제서야 제대로 된 Solution을 찾았다.

---

N=4일 때를 보자. 재풀이 사진을 기준으로 설명한다. 기존에는 파란색 3번부터 막으면 될 줄 알았다. 하지만 그랬다가는 건덕이를 놓쳐버린다.
일단 문제에서 건덕이가 한칸 내려온다는 건 자명하다. 왜냐하면 건덕이는 최선을 다해 움직이므로 반드시 아래로 간다. 그리고 건덕이를 막는 사람 또한 최선을 다해 막아야 하는데, 그렇다면 어디를 막아야 할까? 다 막아보면서 상상을 해보자 그러면 이런 결론이 나온다. 파란색 1번을 제일 먼저 막는게 답이다. 다른 곳을 막아서는 해답이 안나온다. 그런데 파란색 1번을 제일 먼저 막으면, 건덕이가 파란 색 옆 장소까지 아래로 내려왔을 때 파란색 2번으로 막아버리면 된다. 그러면 건덕이를 다시 제일 위로 보내고 다시 내려오게 만들 수 있다. 그러면 총합 8회이다.
N=5일 때도 마찬가지이다. 파란색 1번에 위치하는 장소 즉, 정답의 행보다 한 칸 위의 행에서 세로로 막아버린다. 그리고 나서 건덕이가 파란 색 옆 장소까지 내려올 때까지 기다린다.(막는 사람은 다른 곳에 장벽을 안세우고 파란색 옆장소까지 내려올때까지 기다려야만 한다 그래야 best가 나온다 조급해서 기다리지 않고 장벽을 먼저 세워버리면 건덕이가 오히려 못가는 장소가 생겨버린다) 그리고 건덕이가 옆 장소에 내려왔으면 그 때 파란색 2번처럼 막아버린다. 그러면 칸을 꽉 채워서 건덕이가 다시 올라가고 내려가게 만들 수 있다.

2(N-2) + N-1 + 1 = 3N - 4이다.

#include <bits/stdc++.h>  
using namespace std;  

int N;  

int main() {  
    ios::sync_with_stdio(false);  
    cin.tie(NULL);  
    cout.tie(NULL);  

    cin >> N;  
    if (N <= 3)  
        cout << "0013"[N];  
    else  
        cout << N * 3 - 4;  

}