[C++] 백준 2447번 별 찍기 - 10

분할 정복 / 재귀 문제.

알고리즘 분류를 보고나서, 이 문제를 어떻게 분할 정복 / 재귀로 풀 수 있을까 하는 생각을 많이 했던 것 같다.

규칙을 찾으면 쉽게 풀 수 있던 문제였다.

 

문제풀이

그동안 백준에서 풀어왔던 분할 정복 / 재귀문제는 색종이 자르기와 같이 자기 자신과 같거나 다르면 나누는 문제였다.

그래서 이 문제를 보았을 때 처음에 어떻게 분할해서 나눌수 있을까 생각을 많이했다.

위처럼 그림을 다 그려보고(9x9 그려서 복붙했다.)나서 어떻게 일반화할 수 있을지 생각해보았다.

그리고 어떤 조건에서 '*'이 그려져야 하고, 어떤 조건에서 ' '이 그려져야 하는지 생각해보았다.

아무리 생각해도 조건이 그려지지 않았다. 그래서 다르게 생각해 보았다.

• 어떤 경우에 공백이 그려져야 하는가?

공백이 나오는 경우들만 골라서 생각해보았다. 그래서 다음과 같은 규칙을 얻을 수 있었다.

• 사이즈 3 x 3일 때, 시작점을 (i, j)라 하면 (i + 1, j + 1)에 구멍을 낸다.
• 사이즈 9 x 9일 때, 시작점을 (i, j)라 하면 (i + 3, j + 3)에서 시작해서 3 x 3 모양으로구멍을 낸다.
• 사이즈 27 x 27일 때, 시작점을 (i, j)라 하면 (i + 9, j + 9)에서 시작해서 9 x 9 모양으로 구멍을 낸다.
• ...

즉, 위 규칙을 일반화해서 정리하자면 다음과 같다.

• 사이즈 n x n일 때, 시작점을 (i, j)라 하면 (i + size / 3, j + size / 3)부터 시작해서 (size / 3) x (size / 3) 모양으로 구멍을 낸다.
• 사이즈를 나타내는 n이 3보다 작은 경우에는 고려해주지 않는다.

 

코드를 확인해 보자.

사용한 STL과 변수

가로 세로 길이를 나타내는 widthHeight 변수를 만들었다.

그리고 크기가 3^8까지 가능하므로 그것에 1을 더한 값인 6562크기의 이차원 배열을 만들었다.

메인함수를 보면 알겠지만 board의 요소들은 최초에는 모두 '*'로 초기화시켰다.

 

분할 정복 메서드

분할 정복 메서드는 다음과 같은 구조이다.

• 만일 size가 3보다 작다면 고려할 필요가 없으므로 return한다.
• 이중 for문으로 i의 시작점을 현재좌표 Y에서 size / 3만큼 더해주고, Y 좌표에 2 x (size / 3)을 더하기 바로 직전까지 범위를 설정해준다.
• j의 시작점을 현재 좌표 X에서 size / 3만큼 더해주고, X 좌표에 2 x (size / 3)을 더하기 바로 직전까지 범위를 설정해준다.
• 해당 좌표들의 점을 공백으로 설정한다.

그리고 재귀함수를 호출해서 해당 판을 9등분한 것으로 분할해서 모두 호출해준다.

 

메인함수

가로 세로의 크기를 입력받고, 최초에는 '*'로 모두 초기화해준다.

그리고 check() 분할정복 메서드로 공백이 나와야하는 지점들을 모두 수정해준다.

그리고나서 board 배열을 규격에 맞게 출력해준다.

 

처음에는 cstring STL에 있는 memset() 메서드를 이용해서 초기화했었는데, 좀 더 시간을 줄일 수 없을까하고

이중포문으로 입력받은 크기만큼만 초기화해줬다.

그래서 시간을 20ms나 줄일수 있었다.

 

분할 정복 / 재귀 문제를 봐도 이제 해결할 수 있을 것 같다.

새로운 유형의 문제를 생각해서 풀어봐서 분할 정복을 더 잘 이해할 수 있게됐다.

 

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

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