https://www.acmicpc.net/problem/1780
아이디어
예제를 이용해보자
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
0 1 -1 0 1 -1 0 1 -1
0 -1 1 0 1 -1 0 1 -1
0 1 -1 1 0 -1 0 1 -1
이는 9 x 9인데 이를 3x3으로 바꾼다
하나라도 다른 수가 있으면 그 3x3은 2로 나머지는 모두 같은 수면 그 수로
즉,
0 1 -1
1 0 0
2 2 2
이런 식으로 바꾼다.
그리고 2인 칸은 그 칸의 0 ,1 , -1 개수를 세고 아닌 경우는 세지 않는다.
그리고 이를 축소하면
2이므로
총 개수는 각각
9/9/9
에서 10/12/11 이 된다.
재귀함수로 풀면 더 나을거 같은데
최근 dp문제를 많이 풀어서 그런가 재귀함수로 어떻게 풀지 잘 생각이 나지 않았다.
재귀함수로 푼 코드를 공부해보아야겠다.
#include <stdio.h>
#include <stdlib.h>
int main()
{
int i, j, n, k, l, N;
int same;
int count1 = 0, count0 = 0, countminus = 0;
int temp1, temp0, tempminus;//각 배열을 검사하면서 count에 더할 수도 있는 임시값들
int** temp;// 좀 있다가 나오겠지만 이차원 배열들의 주소들끼리 스왑을 할 것이라 temp가 필요하다.
scanf("%d", &N);
int** paper;
paper = (int**)malloc(sizeof(int*) * N);
for (i = 0; i < N; i++)
{
paper[i] = (int*)malloc(sizeof(int) * N);
}
for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
{
scanf("%d", &paper[i][j]);
}
}
for (n = N / 3; n >= 1; n /= 3)
{
int** array;
array = (int**)malloc(sizeof(int*) * n); //사이즈가 가로세로 원래 배열 나누기 3인 배열을 새로 할당
for (i = 0; i < n; i++)
{
array[i] = (int*)malloc(sizeof(int) * n);
}
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
same = 0;
temp1 = 0;
temp0 = 0;
tempminus = 0;
for (k = 0; k < 3; k++)
{
for (l = 0; l < 3; l++)
{
if (paper[3 * i + k][3 * j + l] == paper[3 * i][3 * j]) same++;// 처음 시작과 배열의 수가 같으면 same++
if (paper[3 * i + k][3 * j + l] == 1) temp1++;
else if (paper[3 * i + k][3 * j + l] == 0) temp0++;
else if (paper[3 * i + k][3 * j + l] == -1) tempminus++; //1,0,-1일 때 각각의 temp값 ++
}
}
if (same == 9 && paper[3 * i][3 * j] != 2)
{
array[i][j] = paper[3 * i][3 * j];
if (n == 1)//n이 1일 때 2가 아니어버리면 개수가 0이 되어버리는 오류가 발생한다. 따라서 조건문 따로 작성
{
if (paper[3 * i][3 * j] == -1)
{
printf("1\n0\n0");
return 0;
}
else if (paper[3 * i][3 * j] == 0)
{
printf("0\n1\n0");
return 0;
}
else
{
printf("0\n0\n1");
return 0;
}
}
}
else
{
array[i][j] = 2; // 배열안의 수가 모두 같지 않으면 새로운 배열에 해당범위의 값을 2로 작성
count1 += temp1;
count0 += temp0;
countminus += tempminus; // 모두 같지 않으므로 temp를 count에 더해준다.
}
}
}
temp = array;
array = paper;
paper = temp;
free(array);
}
printf("%d\n%d\n%d", countminus, count0, count1);
return 0;
}풀면서 배운것
이차원 배열을 malloc으로 만드는 것을 확실하게 배웠다.
일단 정수형 이중 포인터는 왜 int*로 표기할까?
이는 (int) 이라 생각하면 편하다.
int형의 포인터의 자료형이 (int)이니 int의 포인터는 (int)**인 것이다.
그럼 정수형 이차원 배열이 왜 int**인가?
이차원 배열의 각 칸이 정수형 1차원 배열, 즉, 정수형 포인터이기 때문이다.
즉, 이차원 배열로 받은 포인터를 참조했을 때 정수형 포인터가 나오기 때문이다.
따라서 이차원 배열[m][n]의 malloc을 이용한 동적할당은 다음과 같이 한다.
int** array = (int**)malloc(sizeof(int) * m);
for(i = 0; i < m; i++)
{
array[i] = (int*)malloc(sizeof(int) * n);
}재귀함수를 이용한 코드는 이후 이와 거의 유사하다고 하는
https://www.acmicpc.net/problem/1992
이 문제를 통해 직접 작성해보아야겠다.
우선 아이디어는 이러하다.
모두 같으면 그 숫자의 개수를 1더하고
모두 같지 않으면 배열을 9개로 분할하여 다시 검사하는 것이다.
