[분할정복] 백준 2447 - 파이썬

 

의식의 흐름 알고리즘은 문제를 보고 내가 첨에 든 생각들을 끄적인거라 틀린 알고리즘임.

답만 알고 싶다면 최종 알고리즘이나 정답코드만 보면 된다.

 

 

백준 2447.

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

---

의식의 흐름 알고리즘

쉬울거라 생각하고 도전했는데 이게 엔터가 들어가면서부터 뭔가 꼬인다.

 

진짜 재귀 문제 풀수록 자괴감 들어............................................

머릿속에서 대충 돌아는 가는데 그걸 재귀로 구현하는게 정말 쉽지 않다.

특히나 이번문제같은경우는 엔터값도 들어가고 하다보니 더 어려웠음..

원래 생각한 방식은 1 ->3->9로 증가하면서 직전단계 패턴을 그대로 복사해서 중간만 비우고 다른칸에다 채우는건데 그렇게 하면 엔터가 자꾸 값으로 들어가면서 실제 출력할땐 좀 엉망진창이 됨.

 

그냥 대놓고 틀린건데 짠거 + 생각한게 아까워서 그냥 첨부함

def starRecur():
    pattern = "*" 
    spacePattern = " "
    val = int(input())
    res = ""
    
    def recur(pattern, spacePattern,n):
        nonlocal res
        if n > val:
            res = pattern
            return
        res = [[pattern]*3 for _ in range(3)]            
        
        for i in range(0, 3):
            for j in range(0,3):
                if i ==1 and j ==1:
                    res[i][j] = spacePattern
                else:
                    res[i][j] = pattern  
                
        pattern = "".join(res[0]) +"\n"+"".join(res[1])+"\n"+"".join(res[2])
        spacePattern = spacePattern*3+"\n"+spacePattern*3+"\n"+spacePattern*3
        recur(pattern, spacePattern, n*3)

    recur(pattern,spacePattern,3)
    print(res)

 

 

 

최종 알고리즘

약간.. 이걸.. 어떻게.. 떠올리나 싶은.. 그런생각이 든다..

내가 원래 하고자 했던 방식으로 하려면 할 수 있긴하던데 그렇게는 짜다가 헷갈릴 것 같아서 다른 방법을 찾아봤다.

 

3줄단위로 이루어지는 모양이고 가운데는 다르다는 점에서

pattern * 3,

pattern + space + pattern

pattern * 3

이런 수식을 이용한 것 까지는 비슷하다.

다만 해당 pattern을 이차원배열이 아닌 한 줄단위로 취급한 것이 발상의 전환(?)이랄까.

 

이를테면 나는

***

* *

***

이거를 한 패턴으로 놓고 통으로 복사하고 싶었으나 (이게 안됨 - 아까도 말한 엔터때문에)

 

여기서는 for S in Stars 를 통해

s = ***, * *, *** 이걸 카피해서 붙여넣게 한다는 점이 달랐던 것이다.

 

그리고 나는 pattern을 파라미터로 넘기고 싶었는데 여기선 아예 return값으로 넘긴다.

사실 재귀함수 호출 시점이 되게 애매해져서 결국 나는 1->3->9 방식으로 채택했는데

이처럼 하면 보통의 재귀함수처럼 타고타고타고 들어간 후 최소시점부터 완수하며 return 되는 모습을 볼 수 있다.

def starRecur():
    
    def append_star(LEN):
        if LEN == 1:
            return ['*']

        Stars = append_star(LEN//3) 
        L = []  
        
        for S in Stars:
            L.append(S*3)
        for S in Stars:
            L.append(S+' '*(LEN//3)+S)
        for S in Stars:
            L.append(S*3)
        return L

    n = int(sys.stdin.readline().strip())
    print('\n'.join(append_star(n)))