글 읽기 - swap 후 캔디 셀때 왜 전체맵을 다 세야하나요?

jinny 4년 전 1

제가 처음에 짠 로직은

양옆 캔디(위아래 캔디)를 바꾸고, 바꾼 두 캔디 위치의 열과 행에 대해서만 캔디의 길이를 셌습니다.

즉, map[i][j] 캔디와 map[i][j+1] 캔디를 바꾸었으면 i행, j열, j+1열과 같은 행(열) 에 있는 캔디들에 대해서만 최대 캔디 길이를 구했는데, 92%정도에서 자꾸 틀렸다고 나오더라구요.

자꾸 틀려서 찾아보니까 스왑 후 전체 맵을 다 탐색하던데, 바꾸는 행(열)에대해서만 탐색해도 되는거 아닌가요? 다른 부분은 바뀌는 부분이 없다고 생각되는데, 왜 전체를 탐색해야하죠? ㅠㅠ알려주세요

/*사탕 게임*/
#include <iostream>
using namespace std;

int N, maxCandy = 1;
char map[50][51];

void countCandy(int r, int c) {
	int len = 1;
	int maxLen = 0;
	//같은 행에서 제일 긴 길이 찾기
	char candy = map[r][0];
	for (int i = 1; i < N; i++) {
		if (candy == map[r][i])len++;
		else if (i == N - 1 && candy == map[r][i]) {
			len++;
			maxLen = (maxLen < len) ? len : maxLen;
		}
		else {
			maxLen = (maxLen < len) ? len : maxLen;
			len = 1;
			candy = map[r][i];
		}
	}

	//같은 열에서 제일 긴 길이 찾기
	len = 1;
	candy = map[0][c];
	for (int i = 1; i < N; i++) {
		if (candy == map[i][c])len++;
		else if (i == N - 1 && candy == map[i][c]) {
			len++;
			maxLen = (maxLen < len) ? len : maxLen;
		}
		else {
			maxLen = (maxLen < len) ? len : maxLen;
			len = 1;
			candy = map[i][c];
		}
		maxLen = (maxLen < len) ? len : maxLen;

	}

	maxCandy = (maxCandy < maxLen) ? maxLen : maxCandy;
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++)cin >> map[i];

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N-1; j++) {
			//좌우 캔디 바꾸기
			if (map[i][j] != map[i][j + 1]) {
				swap(map[i][j], map[i][j + 1]);
				countCandy(i, j);
				countCandy(i, j + 1);
				swap(map[i][j + 1], map[i][j]);
			}
			//상하 캔디 바꾸기
			if (map[j][i] != map[j + 1][i]) {
				swap(map[j][i], map[j + 1][i]);
				countCandy(j, i);
				countCandy(j + 1, i);
				swap(map[j][i], map[j + 1][i]);
			}
			
		}
	}
	cout << maxCandy << endl;
}

startlink 4년 전 2

바꾼 행과 열이 아닌 곳에 최대 길이가 있을 수도 있기 때문입니다.

rhksdn6227 4년 전 1

CCCC

YDYD

DYDY

YDYD

아래와 같은 경우 어떻게 바꿔도 결국 먹을 수 있는 최대 사탕의 수는 4개입니다.

꼭 바꾼곳에서 최대사탕개수가 나온다고 보장할 수 없습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

swap 후 캔디 셀때 왜 전체맵을 다 세야하나요?

jinny 4년 전 1

startlink 4년 전 2

rhksdn6227 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말