C언어/문제풀다 하나씩

runtimeerror 나서 틀린 문제 고기 뒤집기 OXOOX

mcdn 2020. 6. 4. 21:33
반응형
#include <iostream>
#include <string>
using namespace std;

string pan;

void flipp(int n) {
	int direct[3] = { -1,0,1 };
	for (int i = 0; i < 3;i++) {
		int dy = n + direct[i];
		if (dy >= 0 && dy < 5) {
			if (pan[dy] == 'O') pan[dy] = 'X';
			else if (pan[dy] == 'X') pan[dy] = 'O';
		}
	}
}
int minnn = 10000;
int isitAnser(string t, int len) {
	if (t[0] == 'O') {
		for (int i = 1; i < len;i++) {
			if (t[i] != 'O') return 0;
		}
		return 1;
	}
	else {
		for (int i = 1; i < len;i++) {
			if (t[i] != 'X') return 0;
		}
		return 1;
	}
}
int flag = 0;
int dfs(int lev, int len) {
	//cout << pan << endl;
	if (isitAnser(pan, len) == 1) {
		if (minnn > lev) {
			minnn = lev;
		}
		flag = 1;
		return lev;
	}
	if (lev == len) {
		return flag;
	}
	for (int i = 0; i < 5;i++) {
		flipp(i);
		dfs(lev + 1, len);
	}
	return flag;
}
int main() {
	cin >> pan;
	//flipp(0);
	//cout << pan;
	/// 'OXOOX'
	
	int ret = dfs(0, pan.length());
	if (flag == 0) {
		cout << "impossible";
	}
	else {
		cout << minnn;
	}
	
}



고기의 상태를 입력 받습니다. O는 앞면, X는 뒷면 입니다.

시어머니가 고기를 뒤집을 곳을 지목합니다.
며느리는 시어머니가 지목한 곳과 양쪽 좌우를 모두 뒤집습니다.
아래 예제는 총 두번만에 고기를 모두 같은 방향으로 고기를 뒤집을 수 있습니다.

OXOOX 2nd

XOXOX


만약 시어머니가 가장자리를 선택했다면,
며느리는 2개의 고기만 뒤집습니다.

OXOOX 1st

XOOOX


[입력]
고기의 방향이 입력 됩니다. 
O는 앞면, X는 뒷면으로 두 종류의 입력으로 구성되어 있습니다.

[출력]
모두 같은 방향 (전체 OOOO... 또는 전체 XXXX...) 으로 나오도록 고기를 뒤집을때 가장 적게 뒤집은 수를 출력해주세요.
만약 4회 만에 뒤집는 것을 실패한다면 impossible 이라고 출력 해 주세요.

[세부조건]
고기의 개수는 최대 20개 까지 될 수 있습니다.

 

고기 20개라서 설정한거 

입력 예제

OXOOX

출력 결과

2

반응형