[BOJ] 백준 16720 BAZE RUNNER

문제 링크

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

가장 왼쪽 위에서 출발해 오른쪽 밑으로 도착해야한다.

맨 윗줄과 아랫줄 사이에는 벽들이 있는데, 한 줄당 세 칸의 벽과 한 칸의 통로가 있으며, 한 줄을 통째로 밀어 통로의 위치를 이동시킬 수 있다.

간단하게 풀 수 있다.

우선 현재 위치에서 왼쪽 혹은 위로 가는 경로는 당연히 제외한다.

저 두 상황을 제외한다면 단순히 인접한 길로 이동하는 총 시간은 어떻게 가도 같게된다.

다음으로 어떤 벽을 어떻게 회전시킬지를 결정해야 한다.

통로의 위치를 한 열로 몰아준다.

생각하기 싫어서 1, 2, 3, 4번 열 모두 한 번씩 해본 뒤 가장 작은 값을 구했다.

답을 { 3 (오른쪽으로 이동) + (n - 1) (아래로 이동) + $\sum$ 벽 회전 횟수 } 로 구해줄 수 있다.

정답 코드

	#include <cstdio>
	#include <cmath>
	int n, cnt[4];
	int main() {
	scanf("%d", &n);
	int x;
	for (int i = 0; i < n - 2; i++) {
	for (int j = 0; j < 4; j++) {
	scanf("%1d", &x);
	if (x == 0) cnt[j]++;
	}
	}
	int res = 0, ans = 0x3f3f3f3f;
	for (int i = 0; i < 4; i++) {
	res = 0;
	for (int j = 0; j < 4; j++) {
	if (i == j) continue;
	x = abs(i - j);
	if (x & 1) x = 1;
	res += x * cnt[j];
	}
	ans = ans < res ? ans : res;
	}
	ans += n + 2;
	printf("%d", ans);
	}

view raw 16720.cpp hosted with ❤ by GitHub