[C] 백준 1780번 - 종이의 개수//유지니의 일기1

https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

오늘 내 세상이 무너졌다

 

가로세로 길이랑 -1 0 1 내가 만들어야하는 줄 알고 어제 그것만 계속 하다가 잤는데

아니었던 ,, 것이다

 

#include <stdio.h>
#include <stdlib.h> //srand, rand를 사용하기 위한 헤더파일
#include <time.h> // time을 사용하기 위한 헤더파일

int main()
{
	srand(time(NULL)); // 난수 초기화
	int random = rand() % 6 + 1; 
	int num = 1;

	for (int i = 0; i < random; i++)
		num = num * 3;

	int** arr;
	arr = (int**)malloc(sizeof(int*) * num);

	for (int i = 0; i < num; i++) 
		arr[i] = (int*)malloc(sizeof(int) * num);
	
	int j = 0, k = 0;
	for (int i = 0; i < num * num + num; i++)
	{
		random = rand() % 3;        

		if (j < num)
		{
			arr[k][j] = random - 1; 
			j++;
		}
		else
		{
			j = 0;
			k++; 
		}
	}

	return 0;
}

이중포인터로 이차원 배열 만들고 -1 ~ 1 난수 계속 생성해서 배열에 넣어주는 것까지 한 코드다

하.. 눈에서 눈물이 흐르지만 보내주도록 할게요 😮‍💨😤😮‍💨(연기를 내뿜으며

 

---

어떻게 풀어야할까 고민을 정말 오랫동안 하다가

나는 바보똥꼬라는 것을 깨닫고 얼른 구글링 했다

정말 많은 천재분들을 뵐 수 있었다

 

근데 대부분 c쁠쁠로 하셔서 C로 하신 분 2분의 코드를 봤는데

한 분의 코드가 정말 예술이셔서 그 코드를 참고했다

정말 감사합니다 03ㅡ~❤️

#include <stdio.h>

int arr[2187][2187];
int result[3] = { 0 };

int check(int col, int row, int num);
void divide(int row, int col, int num);

int main()
{
	int input;
	scanf_s("%d", &input);

	int num;
	for (int i = 0; i < input; i++)
	{
		for (int j = 0; j < input; j++)
		{
			scanf_s("%d", &num);
			arr[i][j] = num;
		}
	}

	divide(0, 0, input);
	printf("\n\n%d\n%d\n%d", result[0], result[1], result[2]);

	return 0;
}

int check(int row, int col, int num)
{
	int n = arr[row][col];

	for (int i = row; i < row + num; i++)
	{
		for (int j = col; j < col + num; j++)
		{
			if (n != arr[i][j])
			{
				return 0;
			}
		}
	}
	return 1;
}

void divide(int row, int col, int num)
{
	if (check(row, col, num))
		result[arr[row][col] + 1]++; //arr에 -1,0,1 중에 담겨있을건데 종이에 있을 숫자에 해당하는 인덱스값 1 더해주는 과정
	else
	{
		int size = num / 3;

		for (int i = 0; i < 3; i++)
		{
			for (int j = 0; j < 3; j++)
			{
				divide(row + size * i, col + size * j, size);
			}
		}
	}
}

check 함수에서 

기준 숫자를 하나 잡고 종이 안에 다른 숫자들과 비교를 계속하는데 만약에 다른 숫자 발견하면 return 0 해주고 아니면 return 1해준다

 

처음에 혼자 생각할때 자른거를 다시 배열 만들어서 넣어야하나 하고 두통 앓고 있었는데

check 함수에서 for문 보면

row에서 row + num까지로 해서 

main에서 입력받은 배열을 그대로 이용하되 divide에서 계속 전달받는 파라미터들로 그냥 

엄 음 넹 튼 하는게 좀 멋있었다 휴

 

divide 함수에서

if문에서 check로 그 종이든 잘라진 종이든 기준점을 보내서

1 리턴 받으면 result에서 해당 숫자 인덱스값 해서 올려주고

0 받으면 다시 또 자를건데 그게 else 문에서 나온다

i랑 j가 3까지인 이유는 9등분 해서고

size를 3으로 나눈 이유는 등분 할때마다 종이 사이즈가 1/3배씩 작아져서다

 

휴 오늘도 알찼네용

분할정복 어려운 놈이네용

공부 더 열심히 해야겠어용

아자아자~❤️