[2447번] 별 찍기 - 10

백준 2447번: 별 찍기 - 10

2447번: 별 찍기 - 10

BOJ에 존재하는 별 찍기 문제 중 10번입니다.

 

이 문제의 가장 큰 특징은 '재귀 함수'를 이용한다는 점입니다. 즉 '분할 정복' 문제입니다.

이전 포스팅에서도 분할 정복에 대한 내용은 좀 다뤘으니 tag를 참조해 한 번 보시기 바랍니다.

---

저는 사실 이 문제를 예전에 몇 번 틀렸습니다.

이유는 단순히 재귀의 가장 큰 단점인 시간 초과였죠.

그래서 이를 좀 더 최적화할 방법이 필요하다가 생각했... 지만 그게 아니었습니다.

 

이전에 했던 "생각"은 맞았지만, "구현" 방법의 차이 때문에 쓸데없는 연산이 많았던 것입니다.

그래서 나중에 맞게 푼 방법은 이전 방법에 비해 매우 간단했고, 코드의 길이 또한 3분의 2 정도로 줄였습니다.

---

항상 재귀는 시간 초과가 되지 않도록 구현하는 것이 중요하다는 건 언제나 숙지하고 있었지만, 다시 한번 그 의미를 깨우치게 해 준 문제였습니다.

 

[소스 보기]