[C++] 백준 1074번 Z

1074번: Z

재귀 / 분할 정복 문제.

처음에 풀었던 풀이가 시간초과가 나서 게시판의 도움을 받았다.

게시판의 도움을 받고, 어디가 시간초과가 나는지 알아서 바로 해결해서 제출했더니 맞출 수 있었다.

비효율적이지 않다고 생각했는데도 비효율 적이였다... 시간 줄이는 것은 너무 어려운 일 같다.

 

문제풀이

문제에서 2^n, 재귀라는 말이 주어졌으므로 분할 정복으로 풀어야 한다.

그렇다면 어떻게 분할해서 풀어야 할까?

 

처음에는

2 x 2 사이즈가 되기 전까지는 계속해서 분할한 후에 모든 2x2 사이즈를 탐색하는 방법으로 구현했다.

이렇게 만들면 최대 2^15 * 2^15 = 32,768 * 32,768 = 1,073,741,824의 시간이 걸린다.

문제에서는 0.5초의 시간이 주어졌으므로 50,000,000번 이내로 연산을 끝내야 한다.

 

게시판을 본 후에는

시간초과를 어떻게 줄일 수 있을까? 라는 의문을 가지며 게시판에 반례보다는 시간초과 관련된 질문들을 보았다.

그러던 중 탐색해야 할 부분만 탐색하고, 나머지 부분들은 그냥 더하기만 해주면 된다는 글이 보였다.

 

생각해보니, 굳이 다 탐색할 필요없이, 내가 찾고자 하는 좌표가 있는 곳만 탐색해주면 된다.

탐색할 곳이 아니라면 그냥 해당 크기(사이즈 * 사이즈)를 탐색횟수에 더해주기만 하면 된다.

 

코드를 살펴보자.

사용한 변수와 STL

2^n에서 지수제곱을 하기위한 pow 메서드를 사용하기 위해서 math.h를 include했다.

그리고 입력받는 n, r, c 변수와 현재 칸이 몇번째 탐색인지 저장하는 cnt 변수,

내가 원하는 곳이 몇번째인지 저장하는 ans 변수가 있다.

 

분할 정복 메서드

맨 왼쪽 위 칸의 (y, x)좌표를 입력받고 현재 size를 입력을 받는다.

만일 내가 찾고자 하는 좌표가 현재 정사각형의 범위 안에 있다면,

1. size가 2*2라면 해당 범위에서 찾는다.
2. size가 2*2보다 크다면 다시한번 4방향으로 쪼개준다.

그리고 만일 내가 찾고자 하는 좌표가 현재 정사각형의 범위에 없다면 해당 size에 있는 칸의 개수만큼 탐색횟수에 그냥 더해준다.

cnt는 0부터 시작이고 찾았을 때의 ans값은 cnt부터 시작하므로 0, 1, 2, 3, 4 ...의 범위에 잘 맞게 들어간다.

처음에는 0부터 시작인데 어떻게 더해줘야할까? 고민이 있었는데 큰 문제는 아니였다.

쉽게 말해서 cnt가 다음 칸이 몇번째인지를 미리 나타내고 있다고 생각하면 된다.

 

메인함수

메인함수에서는 n, r, c를 입력받고 

분할 정복 메서드를 실행시킨다.

그리고 ans값을 출력한다.

 

처음에 시간초과난 후에, 코드를 수정하고 디버깅하던 cout 객체를 지우지 못해서 한번 더 틀렸다.

 

분할 정복 문제를 오랜만에 풀었는데 이렇게 모두 탐색하지 않고도 풀 수 있구나 생각이 들었다.

불필요한 탐색을 줄이는 방법도 잘 기억해 놔야겠다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인이 가능하다.