반응형
#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개 까지 될 수 있습니다.
입력 예제
OXOOX
출력 결과
2
반응형
'C언어 > 문제풀다 하나씩' 카테고리의 다른 글
해쉬함수 쓰기! 나이 입력하고 이름 출력 (0) | 2020.06.23 |
---|---|
링크드리스트 int 넣기 myalloc함수 만들어서 넣기 (0) | 2020.06.23 |
링크드리스트 건너건너 출력하기 (0) | 2020.06.23 |
메모리 풀로 링크드리스트 만들기 (3) | 2020.06.23 |
음료 포인트 계산하기 쉬움. (0) | 2020.06.04 |
주변도 같이 사라지는 배열에서 재귀구현 노가다 (0) | 2020.05.29 |
trial and error! 연산자 순열 문제 (0) | 2020.05.29 |
경로 찾기 장애물 있고 (0) | 2020.05.29 |