본문 바로가기

알고리즘/SWEA

2112. 보호 필름

static int D, W, K;
static int board[13][20];
static int injection[13];
static int cpy[13][20];

static bool check()
{
	memcpy(cpy, board, sizeof(board));
	for (int y = 0; y < D; y++)
	{
		if (injection[y] == 2)
			continue;
		//주입 하려는 성분으로 해당 row를 변경
		for (int x = 0; x < W; x++)
			cpy[y][x] = injection[y];
	}

	for (int x = 0; x < W; x++)
	{
		int priv = cpy[0][x], cnt = 1;
		for (int y = 1; y < D; y++)
		{
			if (priv == cpy[y][x])
				cnt += 1;
			else //다르면
			{
				priv = cpy[y][x]; //다시 초기화
				cnt = 1;
			}
			if (cnt >= K) //조건 만족
				break;
		}
		if (cnt < K) //어떤 x가 검사를 통과하지 못함.
			return false;
	}
	//모든 x에 대해서 검사를 통과
	return true;
}

static bool __solution(int y, int cnt, int ans)
{
	//배열의 인덱스로 사용하는 값이
	//해당 배열을 벗어나는지 체크 하는 것을 가장 먼저
	//해주어야만 한다.
	if (y >= D && cnt < ans)
		return false;

	//현재 정하려는 개수만큼 채웠다면
	if (cnt >= ans)
	{
		//나머지는 전부 바꾸지 않음
		for (int i = y; i < D; i++)
			injection[i] = 2;
		return check();
	}
	//앞으로 y가 부족하다면
	else if (ans - cnt > D - y) 
		return false;
	else
	{
		//특성 A(0), 특성 B(1)
		for (int i = 0; i < 2; i++)
		{
			injection[y] = i;
			bool ret = __solution(y + 1, cnt + 1, ans);
			if (ret == true)
				return true;
		}
		injection[y] = 2; //not change
		return __solution(y + 1, cnt, ans);
	}
}

static int solution()
{
	int ret = 0;

	scanf("%d %d %d", &D, &W, &K);
	for (int y = 0; y < D; y++)
	{
		for (int x = 0; x < W; x++)
		{
			scanf("%d", &board[y][x]);
		}
	}

	for (int k = 0; k < D; k++)
	{
		if (__solution(0, 0, k))
			return k;
	}

	return D;
}

재귀 함수 사용 시 배열에 무언가 정보를 채워넣는 경우,

해당 배열에 사용 할 인덱스가 배열의 범위를 넘어서지 않게 이에 대한 점검을 가장 먼저 해줄 것.

 

VS는 gcc보다 좀 더 관대하므로, VS에서 테스트 시 결과가 정상적으로 나오면 괜찮지만,

결과가 좀 이상 하면 gcc에서 테스트해보고,

 

테스트 시 정상적으로 동작하면 로직 오류

segmentation falut -> 배열 범위 오류

memory exceed -> 스택 오버플로우(재귀 횟수 단축 고민)

 

이 정도를 염두할 것

'알고리즘 > SWEA' 카테고리의 다른 글

5648. 원자 소멸 시뮬레이션  (0) 2021.11.11
1953. 탈주범 검거  (0) 2021.11.11
2105. 디저트 카페  (0) 2021.11.11
2382. 미생물 격리  (0) 2021.11.09
2383. 점심 식사시간  (0) 2021.11.09