67. 백준 : Z

 

이것도 분할 정복인 것 같은데

이전 문제랑 비슷하게 가볼까

 

📌 초기 구상

1) 입력 받고, N에 맞게 보드 만들기

2) 탐색 , 네모 사이즈가 N==1 일 때까지 분할하기

3) N==1 이면, 그 사각형에 순서대로 업데이트

 

 

당연히 안 된다.

- 재귀가 순서대로 들어간다는 보장도 없고 (근데 결과보면 순서대로는 되어 있음)

- 어찌저찌 된 것 같긴한데 완벽하진 않다.

 

 

생각대로는 돌아가는데 겹치고 있다.

자르는 구간을 좀 더 지능적으로 해야할 것 같다.

 

단계별로는 사이즈를 -1 씩 줄이는데

또 자르는 크기 처리는 //2로 하고 있어서 그런 듯하다.

 

자르는 거랑 사이즈 분별을 나눠서 넘겨주자.

 

이렇게 나눠서 넘겨주면 될 듯

 

모든 케이스 통과!

 

엄

---

DP를 쓰면 안 될 것 같다.

 

그냥 해당 위치를 찾았다면 cnt를 출력하고 끝내는 방식이 맞는 것 같다.

 

📌 재구상

크기를 줄이는 것까지는 방식이 같다.

바꿔야 하는 건 카운트 하는 거다.

DP로 카운트 하는 게 아니라, 도착지까지 가는데 발생하는 cost를 하나의 변수에 담아두면 된다.

DP ➡️ 하나의 변수

 

1) [ 종료 조건 ]우선 search에서 i,j == r,C 라면 반환

2) 현재 search하려고 분할된 곳에 r,C가 없다면?
     > 현재 탐색중인 사분면의 사이즈만큼 더하고 끝낸다.
    ( size가 1이 되어도 1*1이므로 예외케이스는 없다 )

3) 1,2에서 다 걸리지 않았다면 현재 탐색 size에서 4개의 사분면으로 나눈다.

 

---

분할 정복은 계속 해봐야겠다.

이젠 슬슬 메모리도 조금 생각하면서 해야할 정도로 난이도가 올라가는 것 같다.

 

레벨 4까지는 안전하게 풀 수 있을 정도로 올려두자