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 |