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

 

범위를 체크하는데 숫자를 잘못써서 조금 애먹고 배열을 초기화를 잘못해줘서 너무 오래걸렸던 문제이다 ㅠㅠ 알고리즘

 

자체는 처음에 설계한 것이 작동되는게 맞는데 저러한 사소한 실수들로 인해 너무나도 시간을 많이 잡아먹었다. 아마 내가 

 

설계한 알고리즘 자체가 조금은 범위 설정이나 이런 면에 있어 복잡하기 때문에 그럴 수도 있다.

 

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

2447번: 별 찍기 - 10

 

우선 문제를 보고 가자.

 

문제에서 일단 크나큰 힌트를 줬다. 재귀(recursion)라는 힌트를 줬다!

 

게다가 문제 자체가 우선 3x3 정사각형에서 차츰차츰 넓혀가는 형태이기 때문에 분할정복(divide and conquer)이라는 것

 

을 바로 알 수 있었다.

 

 

문제를 먼저 이해해보자면 N이 주어지면 NxN 정사각형 모양의 별찍기에서 N / 3 x N / 3 의 부분은 별이 비어있는 형태이

 

다. 그리고 그 부분을 제외한 나머지 부분 들은 그 전 단계인 N / 3 x N / 3 정사각형 모양의 별찍기로 채우는 것이다. 백문이

 

불여일견 이므로 사진을 참고하자.

 

직접 그려서 그림 상태가 조금 안좋은 점 이해바란다.

 

이런 식으로 별을 찍어내면 된다.

 

사실 문제에서 재귀를 주기는 했지만 분할 정복을 통해 해결해야 함을 알면 재귀를 사용하는 것이 편하다는 것을 금방 알

 

수 있을 것이다. 실제로 나도 문제에서 재귀라고 주어진 것을 못보고 분할 정복을 통해 설계하다보니 재귀를 사용해야겠다

 

고 깨달았다.

 

이제 분할정복과 재귀를 활용하면 되는 것을 알았으니 코드를 살펴보자.

 

우선 주어진 N 에 대하여  N / 3 x N / 3 부분만 삭제된 별찍기 정사각형을 배열에 저장해주었다.

 

그런 다음 재귀를 활용하여 차례대로 위에서부터 좌표 순서대로 N / 3 x N / 3의 별찍기 정사각형을 저장하게끔 재귀를 호

 

출하였다. 만일 이렇게 호출된 N / 3 x N / 3 정사각형이 3 x 3 정사각형이 아닐 경우 계속해서 재귀를 호출하여 n / 3 x n / 3

 

번째가 모두 삭제된 별찍기 정사각형을 채운다. 작은 것부터 해결하여 큰 것을 해결하는 분할 정복 알고리즘을 사용한 부분

 

이다. 그런데 이 때 범위 설정에 매우 유의하기 바란다. 이렇게 코드를 짜면 범위를 설정할 때 숫자를 쓰기 조금은 까다로워

 

지기 때문에 특히 유의 바란다, 코드가 생각보다 심플하기 때문에 설명은 여기서 마친다!