티스토리 뷰

반응형

문제보기

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

분할정복 문제


재귀에 대해 능숙하다면 금방 해결 할 수 있는 문제이다. 10~20분 소요.

나는 알고리즘을 처음 시작할 때가 작년 7월 정도였으니, 한 9개월 정도 공부한 것이다.

내가 별찍기 11을 작년 8월- 그러니까 한 알고리즘 시작한지 1개월 도 안되었을 때 도전했다가 실패했을 것이다. 그때 좀 우울했다.

그러니까 이 문제를 해결하고, 포스팅 하는거지만,.. 나에겐 의미가 있는 포스팅이다 ㅋ.
  

이런류의 또 이런 수준의 문제는 다른사람의 코드를 보고 이해하고 분석하고 왜 틀린 이유를 짚으려면 나에겐 아직 조금 난해하기도 하고, 어렵다

그런만큼 초보 수준에서 별찍기 마스터를 하겠다 해서 괜히 이런문제에 상처받질 않기를 원한다.

왜냐하면 별찍기 문제를 풀겠다고 했다가 괜히 이문제에 상처받고 공부를 하지 않으시는 분들이
있을것 같기 때문이다.

현직자 분들중에서도 백준 문제가 어렵다고 하셔서, 왠지 이런 기초같은 응용문제를 도전하다가 마음의 상처를 얻으신거 같긴한데,

이런 문제를 보았을 때 아 재귀로도 의미 있게 할 수 있구나

생각하시고, 

분할정복이 너무 어렵다면, 특히 대표적인 문제 - 하노이, 별찍기 -는 재귀 기초적 사용을 익히기 위해서는 쉬운 문제가 아니다.

그러니까, DFS 탐색과 완전 기초 DP부터 시작하는 것이 재귀에 익숙해지는 좋은 방법일 수 있다. 

사람마다 느끼는게다르겠지만, 난 그렇게 생각한다.


근데 왜 딴소리만 늘어놨지,


문제 해결은 간단하다.

1개의 함수는 9번의 함수를 call 한다. 왜냐하면

딱봤을때 1개 말고 9개 들어오면, 바로 9개 호출해야할것 같기때문이다.
그리고 그림상 봤을때 뭔가  ( 별, 별 , 별 / 별, 공백, 별/ 별, 별, 별) 구조를 띄기 때문에, 9개로 나눠야할 것 같았기때문이다.
그리고 각 함수는 또 자신의 9개 call을 한다. 이때 공백으로 들어 온것은 절대적으로 공백이여야하고
나머지 별 을 받은 곳은 또 그곳 안에서 ( 별, 별, 별/ 별, 공백 , 별/ 별, 별, 별) 로 호출될수있다.

n==1 일때, 그러니까 가장 작은 크기일때 그제서야 s[x][y] = 문자 (별 또는 공백) 을 넣는다.

이 이외의 설명은 소스를 보면 알 수 있다. 특히 x, y의 좌표상태가 함수를 통해 내려가는것 등.

소스보기




반응형

'알고리즘 문제 > DFS and Simillar' 카테고리의 다른 글

백준 12784 인하니카 공화국  (0) 2018.05.29
884C Bertown Subway  (0) 2017.11.05
BoJ 1717 : 집합의 표현  (0) 2017.10.29