C++ / 백준 / 27165 / 모든 곳을 안전하게

문제

 

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

27165번: 모든 곳을 안전하게

 

문제풀이

 

0부터 N번까지의 N+1개의 칸이 있다.

0부터 N번까지의 칸에는 말들이 놓여있거나 놓여있지 않다.

말들이 모든 칸에 2개 이상 or 0개가 있을 경우 안전한 상태라 한다.

 

주어진 입력에서 안전한 상태가 될 수 있는지, 안전한 상태라면 어느 칸의 말을 옮겨야 하는지 출력하는 문제이다.

 

경우의 수를 나누어 문제를 풀었다.

입력을 받을 때 말의 칸이 1인 경우 1의 개수를 나타내는 변수에 1을 더한다.

그리고 1의 위치를 저장하는 변수에는 한번만 위치를 저장한다.

 

1의 개수에 따라 조건을 4개로 나눌 수 있다.

 

1의 개수가 2개 초과일때, 안전한 상태를 만들 수 없다.

 

1의 개수가 2개일때, 둘의 위치의 차가 X면 안전한 상태가 가능하고, X가 아니라면 안전한 상태를 만들 수 없다.

 

1의 개수가 1개일때, 해당 위치 - X의 값이 3 이상이면, 1개만 있는 말을 왼쪽을 옮기면 안전한 상태가 가능하다.

또는 해당 위치 + X의 값이 1이상이면, 1개만 있는 말을 오른쪽으로 옮기면 안전한 상태가 가능하다.

 

마지막으로는 1의 개수가 0개 일때, 남은 주사위 눈은 무조건 사용해야 한다.

반복문을 통해 현재 위치에 있는 말이 3개 이상이고, 위치 + X칸에 있는 말이 0개가 아닌 경우, 오른쪽으로 옮기면 안전한 상태가 가능하다.

 

 

 

 

코드

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

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

	int N(0), X(0), one_idx(0), one_cnt(0);
	cin >> N;

	vector<int>board(N + 1, 0);
	for (int idx = 0; idx <= N; ++idx) {
		cin >> board[idx];
		if (board[idx] == 1) {
			++one_cnt;
			if (one_cnt == 1) one_idx = idx;
		}
	}

	bool answer(false);
	int loc1(0), loc2(0);
	cin >> X;

	if (one_cnt > 2) answer = false;
	else if (one_cnt == 2) {
		if (one_idx + X <= N && board[one_idx + X] == 1) {
			answer = true;
			loc1 = one_idx;
			loc2 = one_idx + X;
		}
		else answer = false;
	}
	else if (one_cnt == 1) {
		if (one_idx + X <= N && board[one_idx + X] >= 1) {
			answer = true;
			loc1 = one_idx;
			loc2 = one_idx + X;
		}
		else if (one_idx - X >= 0 && board[one_idx - X] >= 3) {
			answer = true;
			loc1 = one_idx - X;
			loc2 = one_idx;
		}
		else answer = false;
	}
	else {
		for (int idx = 0; idx + X <= N; ++idx) {
			if (board[idx] > 2 && board[idx + X] >= 1) {
				answer = true;
				loc1 = idx;
				loc2 = idx + X;
				break;
			}
		}
	}

	if (answer == true) {
		cout << "YES\n";
		cout << loc1 << " " << loc2;
	}
	else cout << "NO";
}