66. 백준 : 색종이 만들기

 

꽤 복잡해보인다.

하지만? 들이박고자 하면 할만함

 

우선 정사각형 크기의 색종이를 얻고자 한다.

그 사각형의 넓이가 1,2,4,8,16,... 2^n 로 될 수 있다.

 

📌초기 구상

1) 일단 그럼 사각형의 크기를 N으로 입력받았다고 하면

N을 기준으로 1,2,3,4 사분면을 나눈다.

 

2) 해당 사분면을 돌면서 하나의 숫자만 있는지 본다.

   > 시작 부분의 숫자를 변수에 담고, 그 뒤에 이거랑 다른 애가 있는지 본다는 뜻

 

3) 다른 게 있다면, 탐색을 하는 부분에서 4개의 사분면으로 나눈다!

 

여기서부터 N은 색종이로 채택될 사각형의 넓이라고 해주자...

 

우선 가장 첫 위치 값을 기준으로 잡고 i,j로 모든 위치를 다 돈다.

근데 0,2 위치에서 기준과 다른 값을 만난다.

 

➡️ 현재 범위에서 4개의 사분면으로 나눈다.

이렇게 나눠서 처음 기준과 다른 값이 있는지 판단한다.

1사분면을 제외하고는 모두 1이 기준이다.

그리고 이 단계에서는 4사분면만 통과하여 파란색 종이가 Plus 된다.

> 통과했다는 건, 해당 사분면을 모두 돌았을 때 기준값과 같았다는 뜻!

 

 

나머지 사분면에서는 또 돌릴 것이다.

 

이번에는 채택되는 사각형들이 꽤 많다.

2,0 사각형만 한 번 더 해야함

 

이런 매커니즘으로 작동한다고 생각하고 코드를 보자.

 

---

분할 집합 문제는 구역을 나누거나 카운트 하는 조건이 가장 중요한 것 같다.

문제를 계속 풀어보는 게 관건이지만,,, 분할 집합 가장 쉬운 문제가 실버1인 걸 보면

기본적으로 어려운가보다! 계속 해보자~~