백준 16720번 BAZE RUNNER

문제 링크입니다: https://www.acmicpc.net/problem/16720

간단한 브루트 포스(Brute Force) 문제였습니다.

알고리즘은 아래와 같습니다.

1. 벽을 움직이는 횟수와 상관 없이 오른쪽으로 3칸, 아래로 (N - 1)칸 가는 것은 고정이기 때문에 결과는 (N + 2)로 시작합니다.

2. 벽을 얼만큼 밀지를 결정하는데 각 높이마다 최대 2번 움직입니다.

-> 이유는 3번 움직일 경우 반대 방향으로 1번만 움직이면 되기 때문입니다.

3. 벽을 민 횟수 + (N + 2)를 출력해줍니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 1000;

const int INF = 987654321;

 

int col[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        for(int i=0; i<N-2; i++)

                 for (int j = 0; j < 4; j++)

                 {

                         char c;

                         cin >> c;

 

                         if (c == '0')

                                 col[i] = j; //통로 표시

                 }

 

        int result = INF;

        for (int i = 0; i < 4; i++)

        {

                 int sum = 0;

                 for (int j = 0; j < N - 2; j++)

                 {

                         int temp = abs(col[j] - i);

                         //우 3 = 좌 1, 좌 3 = 우 1

                         sum += (temp == 3 ? 1 : temp);

                 }

                 result = min(result, sum);

        }

        //우 3, 하 (N - 1)

        cout << 3 + (N - 1) + result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~