[python_파이썬]백준_2903번_중앙이동알고리즘_풀이

처음 이 문제를 접했을때 배열로 풀어야 하나? 고민했다.
 
지금 내 문제는 문제를 처음 직면 했을 때 어떻게 접근해야 할지 막막하다. 일단 최대한 많은 문제를 접하면서 어떻게든 경험치를 쌓는게 중요할 것 같다.
 
4개의 점으로 만들어진 정사각형이 증식하면서 이런 모양으로 바뀌는데 이걸 어떻게 접근해야 할지 자체가 너무 막막했다.
왠만하면 다른 문제를 풀기 전에 다른 질문게시판을 이용하지 않지만, 어떻게 접근해야 할지 감이 잡히지 않아서 참고했다.

 
자. 이제 해보자. 
0번 = 4개
1번 => 9개
2번 => 25개
3번 => ???
이렇게 되겠지.
 
배열 접근은 말이 안되는 것 같고, 
처음 한변에 점이 2개가 기본이고, 1번 거칠때 3개가 되고, 2번 거치니까 5개(3 + 2)가 된다.
3번 거칠 경우 9개(5 + 4).
4번 거칠 경우 17개 (9 + 8)
단순히 2개의 점에서 출발할 경우 2 + 1, 3 + 2, 5 + 4, 9 + 8 이렇게 반복 된다.
그냥 현재의 점에서 -1를 해주면 가운데 점을 추가하는 효과가 나온다.
 
초기 : 2 * 2
1번 : 3 * 2
2번 : 5 * 2
3번 : 9 * 2
4번 : 17 * 2
 
이렇게 된다 치고 한번 코드를 작성해 보자.
1. 일단 ** 2 : 제곱은 무조건 되는 걸로 생각한다.
2. 반복되는게 2, 3, 5, 9, 17....... 여기에서 공통요소를 찾는다.
3. 2번의 공통요소 : 1, 2, 4, 8 이렇게 증가한다.
4. 2 ** 0, 2 ** 1, 2 ** 2, 2 ** 3..... 이렇게 공통 요소를 파악한다. (사실 이 공통 요소를 찾는것도 나한테는 힘들다.)
근데 이걸 쭉 봤을 때 어? 이건 재귀함수인데? 가 딱 떠오른다. 최근에 DFS 온라인 강의를 봐서 머리에 배열이랑 재귀가 많이 생각난다.
 
조금 더 생각을 해보면 처음 공부할때 하오이 게임, sum()재귀, 피보나치수열 등이 생각나면서 재귀로 풀이를 고민했다.
 
그럼 다시 고민해보자.
 
1번 : 3 = 2 + 2 ** 0 // 2 + 1
2번 : 5 = 2 + 2 ** 0 + 2 ** 1 // 2 + 1 + 2
3번 : 9 = 2 + 2 ** 0 + 2 ** 1 + 2 ** 2 // 2 + 1 + 2 + 4
4번 : 17 = 2 + 2 ** 0 + 2 ** 1 + 2 ** 2 + 2 ** 3 // 2 + 1 + 2 + 4 + 8
오 이 규칙은 무조건 재귀함수가 걸린다고 생각되었다.  

import sys

input = sys.stdin.readline

def move(N):

    if N == 1:

        return 2 + 2 ** (N - 1)

    else:

        return move(N-1) + 2 ** (N - 1)

N = int(input())

answer = move(N)

print(answer ** 2)

 
일단 기본적으로 N이 1부터 시작할때 3을 만들어 줘야 하니까 2 + 2 ** (N -1)로 시작했다.
그리고 else조건으로 (N - 1)조건으로 (2-1)이 되면 N = 1일때 값이 재귀로 나오고, + 2 ** (2-1)이 되니까 
N = 2일때 재귀가 성립된다.
 
N = 3일때도 move(2) + 2 ** (3-1)이 나와서 코드가 맞게 나온다.
 
즉, 재귀함수로 해결했다.
 
----------------------------------------------------------------------------------------------------------
<다른 풀이>
1번 : 3
2번 : 5
3번 : 9
4번 : 17
공통요소를 다시 뽑으면
1번 : 1 + 2 ==> 2 ** 1
2번 : 1 + 4 == > 2 ** 2
3번 : 1 + 8 ==> 2 ** 3
4번 : 1 + 16 == > 2 ** 4
이렇게 나온다. 
 
나는 왜 이게 바로 생각이 안날까..........

import sys

input = sys.stdin.readline

N = int(input())

print((2 ** N + 1) ** 2)

 
근데 이 문제를 또 보면 풀 수 있을까...... 일단 계속 도전해보자.
 
공부하는 허딩크 : https://www.youtube.com/live/Oxb1EL00IUA?feature=shared