[BOJ] 3085_사탕게임

ProblemSolving / / 2021. 2. 3. 16:27

사탕게임

문제 링크: https://www.acmicpc.net/problem/3085

 

3085번: 사탕 게임

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

www.acmicpc.net

그냥 단순히 하나의 요소를 바꾸었을 때 마다 전체 배열을 전체 둘러보고 가장 긴 막대를 찾는다.

 

  • 정답 코드

      #include<iostream>
  #include<deque>
  #include<algorithm>
  using namespace std;
  #define max(a,b) (a>b?a:b);

  int n;
  int board[51][51];

  int check() {
      deque<int> candy;
      int maxNum = 0;

      //행 탐색
      for (int y = 0; y < n; y++) {
          for (int x = 0; x < n; x++) {
              if (candy.empty())
                  candy.push_back(board[y][x]);
              else {
                  if (candy.back() == board[y][x])
                      candy.push_back(board[y][x]);
                  else {
                      maxNum = max(maxNum, candy.size());
                      candy.clear();
                      candy.push_back(board[y][x]);
                  }
              }
          }
          maxNum = max(maxNum, candy.size());
          candy.clear();
      }

      //열 탐색
      for (int x = 0; x < n; x++) {
          for (int y = 0; y < n; y++) {
              if (candy.empty())
                  candy.push_back(board[y][x]);
              else {
                  if (candy.back() == board[y][x])
                      candy.push_back(board[y][x]);
                  else {
                      maxNum = max(maxNum, candy.size());
                      candy.clear();
                      candy.push_back(board[y][x]);
                  }
              }
          }
          maxNum = max(maxNum, candy.size());
          candy.clear();
      }

      return maxNum;
  }

  int main() {
      cin >> n;

      for (int y = 0; y < n; y++)
          for (int x = 0; x < n; x++) {
              char temp;
              int te = 0;
              cin >> temp;
              switch (temp) {
              case 'C':
                  te = 1;
                  break;
              case 'P':
                  te = 2;
                  break;
              case 'Z':
                  te = 3;
                  break;
              case 'Y':
                  te = 4;
                  break;
              }
              board[y][x] = te;
          }

      int maxNum = check();

      for (int y = 0; y < n; y++)
          for (int x = 0; x < n; x++) {
              swap(board[y][x], board[y][x + 1]);
              maxNum = max(maxNum, check());
              swap(board[y][x], board[y][x + 1]);

              swap(board[y][x], board[y + 1][x]);
              maxNum = max(maxNum, check());
              swap(board[y][x], board[y + 1][x]);
          }

      cout << maxNum << endl;

      return 0;
  }

 

ps. 정말 오랫동안 고민했던 코드이다.
이 코드는 swap을 하지 않고 각 요소마다 만들 수 있는 가장 긴 막대를 찾아 데이터를 저장하는 것이다.
만들 수 있는 막대라 함은 바꿀 수 있는 기회가 한 번이므로 자신의 데이터를 기준으로 한 줄씩 체크를 하되, 한번 끊기게 된 경우, swap할 수 있는 경우를 찾는다.
swap할 수 있는 경우가 있을 때 해당 데이터를 가져오고 이어서 탐색을 진행한다.
만일 더 이상 가져올 수 있는 데이터가 없을 경우 현재 값이 가장 최고값임을 이해하고 해당 길이를 반환한다.

 

아직 이 코드의 실패 원인을 찾지 못하였다.
계속 93%에서 실패로 뜨길래 결국 이 코드를 포기하고 말았다.

  • 실패 코드 
    #include<iostream>
#include<stack>
using namespace std;
#define max(a,b) (a>b?a:b);

int n;
pair<int,int> board[51][51];

//flag 변수는 swap을 한번 할 수 있는 기회

int RowCheck(int x_, int y) {
	stack<int>row;
	bool flag = true;
	int maxSize = 0;
	
	row.push(board[y][x_].first);

	for (int x = x_; x < n; x++) {
		if (!row.empty()) {
			if (row.top() == board[y][x].first)
				row.push(board[y][x].first);
			else if (flag && (x + 1 < n)) {
				if (row.top() == board[y][x + 1].first) {
					if ((y + 1 < n) && (row.top() == board[y + 1][x].first)) {
						row.push(board[y + 1][x].first);
						flag = false;
					}
					else if ((y - 1 >= 0) && (row.top() == board[y - 1][x].first)) {
						row.push(board[y - 1][x].first);
						flag = false;
					}
					else {
						row.push(board[y][x + 1].first);
						maxSize = max(maxSize, row.size());
						return maxSize;
					}
				}
				else {
					if ((y + 1 < n) && (row.top() == board[y + 1][x + 1].first)) 
						row.push(board[y + 1][x+1].first);
					else if ((y - 1 >= 0) && (row.top() == board[y - 1][x + 1].first)) 
						row.push(board[y - 1][x+1].first);
					maxSize = max(maxSize, row.size()-1);
					return maxSize;
				}
			}
			else {
				maxSize = max(maxSize, row.size()-1);
				return maxSize;
			}
		}
		else
			row.push(board[y][x].first);
	}
	maxSize = max(maxSize, row.size()-1);
	return maxSize;
}
int ColCheck(int x, int y_) {
	stack<int>col;
	bool flag = true;
	int maxSize = 0;
	col.push(board[y_][x].first);
	for (int y = y_; y < n; y++) {
		if (!col.empty()) {
			if (col.top() == board[y][x].first)
				col.push(board[y][x].first);
			else if (flag && (y + 1 < n)) {
				if (col.top() == board[y + 1][x].first) {
					//중간에 하나가 끊긴 케이스
					if ((x + 1 < n) && (col.top() == board[y][x + 1].first)) {
						col.push(board[y][x + 1].first);
						flag = false;
					}
					else if ((x - 1 >= 0) && (col.top() == board[y][x - 1].first)) {
						col.push(board[y][x - 1].first);
						flag = false;
					}
					else {
						col.push(board[y + 1][x].first);
						maxSize = max(maxSize, col.size()-1);
						return maxSize;
					}
				}
				else {
					if ((x + 1 < n) && (col.top() == board[y + 1][x + 1].first)) 
						col.push(board[y + 1][x + 1].first);
					else if ((x - 1 >= 0) && (col.top() == board[y + 1][x - 1].first))
						col.push(board[y + 1][x - 1].first);

					maxSize = max(maxSize, col.size() - 1);
					return maxSize;
				}
			}
			else {
				maxSize = max(maxSize, col.size() - 1);
				return maxSize;
			}
		}
		else
			col.push(board[y][x].first);
	}
	maxSize = max(maxSize, col.size() - 1);
	return maxSize;
}

int ReverseRowCheck(int x_, int y) {
	stack<int>row;
	bool flag = true;
	int maxSize = 0;

	row.push(board[y][x_].first);

	for (int x = x_; x >= 0; x--) {
		if (!row.empty()) {
			if (row.top() == board[y][x].first)
				row.push(board[y][x].first);
			else if (flag && (x - 1 >= 0) ) {
				if ( row.top() == board[y][x - 1].first) {
					if ((y + 1 < n) && (row.top() == board[y + 1][x].first)) {
						row.push(board[y + 1][x].first);
						flag = false;
					}
					else if ((y - 1 >= 0) && (row.top() == board[y - 1][x].first)) {
						row.push(board[y - 1][x].first);
						flag = false;
					}
					else {
						row.push(board[y][x - 1].first);
						maxSize = max(maxSize, row.size());
						return maxSize;
					}
				}
				else {
					if ((y + 1 < n) && (row.top() == board[y + 1][x - 1].first))
						row.push(board[y + 1][x - 1].first);
					else if ((y - 1 >= 0) && (row.top() == board[y - 1][x - 1].first))
						row.push(board[y - 1][x - 1].first);

					maxSize = max(maxSize, row.size() - 1);
					return maxSize;
				}
			}
			else {
				maxSize = max(maxSize, row.size() - 1);
				return maxSize;
			}
		}
		else
			row.push(board[y][x].first);
	}
	maxSize = max(maxSize, row.size() - 1);
	return maxSize;
}
int ReverseColCheck(int x, int y_) {
	stack<int>col;
	bool flag = true;
	int maxSize = 0;
	col.push(board[y_][x].first);
	for (int y = y_; y >= 0; y--) {
		if (!col.empty()) {
			if (col.top() == board[y][x].first)
				col.push(board[y][x].first);
			else if (flag && (y - 1 >= 0) ) {
				if (col.top() == board[y - 1][x].first) {
					//중간에 하나가 끊긴 케이스
					if ((x + 1 < n) && (col.top() == board[y][x + 1].first)) {
						col.push(board[y][x + 1].first);
						flag = false;
					}
					else if ((x - 1 >= 0) && (col.top() == board[y][x - 1].first)) {
						col.push(board[y][x - 1].first);
						flag = false;
					}
					else {
						col.push(board[y - 1][x].first);
						maxSize = max(maxSize, col.size() - 1);
						return maxSize;
					}
				}
				else {
					if ((x + 1 < n) && (col.top() == board[y - 1][x + 1].first))
						col.push(board[y - 1][x + 1].first);
					else if ((x - 1 >= 0) && (col.top() == board[y - 1][x - 1].first))
						col.push(board[y - 1][x - 1].first);

					maxSize = max(maxSize, col.size() - 1);
					return maxSize;
				}
			}
			else {
				maxSize = max(maxSize, col.size() - 1);
				return maxSize;
			}
		}
		else
			col.push(board[y][x].first);
	}
	maxSize = max(maxSize, col.size() - 1);
	return maxSize;
}


int main() {
	cin >> n;

	for (int y = 0; y < n; y++)
		for (int x = 0; x < n; x++) {
			char temp;
			int te = 0;
			cin >> temp;
			switch (temp) {
			case 'C':
				te = 1;
				break;
			case 'P':
				te = 2;
				break;
			case 'Z':
				te = 3;
				break;
			case 'Y':
				te = 4;
				break;
			}
			board[y][x].first = te;
		}

	int maxNum = 0;
	for (int y = 0; y < n; y++)
		for (int x = 0; x < n; x++) {
			int a = RowCheck(x, y), b = ColCheck(x, y);
			int c = ReverseRowCheck(x, y), d = ReverseColCheck(x, y);
			cout << y << "," << x << " : " << a << " " << b << " " << c << " " << d << endl;
			int temp1 = max(a, b);
			int temp2 = max(c, d);
			board[y][x].second = max(temp1, temp2);
			maxNum = max(maxNum, board[y][x].second);
		}

	cout << maxNum << endl;

	return 0;
}
저작자표시 비영리 동일조건

'ProblemSolving' 카테고리의 다른 글

[BOJ] 7785_회사에 있는 사람  (0) 2021.02.05
[BOJ] 5397_키로커  (0) 2021.02.04
[BOJ] 1074_Z  (0) 2021.02.02
[BOJ] 1309_동물원  (0) 2021.02.01
[BOJ] 1564_팩토리얼5  (0) 2021.01.31
  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기
ProblemSolving 관련 글
글 더보기

티스토리툴바