알고리즘/Dynamic Programming
프로그래머스 ) 종이접기
개발자가될수있을까?
2020. 1. 26. 14:38
종이를 반씩 접으면서 튀어나온 부분은 1 들어간 부분은 0 으로한 배열을 리턴하는 문제이다.
어떻게 이런 문제를 낼 생각을 했을까..
직접 접어봐도 되고, 여러 방법으로
규칙을 찾으면
n번째 배열은 n-1 + 0 + n-1(변형)
의 규칙이 있는 것을 알수있다.
뒤쪽 n-1에서 배열길이의 /2에 해당되는 위치의 값이 1로 바뀌는것을 알수있다.
파이썬으로 풀어달라는 x예찬님의 요청으로 파이썬으로 풀었다
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
answer = [ [] for i in range(21)]
visit = [False for i in range(21)]
answer[1] = [0]
answer[2] = [0,0,1]
visit[1] = True
visit[2] = True
def solution(n):
if(visit[n]):
return answer[n]
else :
visit[n] = True
answer[n] = solution(n-1) + [0] + solution(n-1)
length = len(answer[n-1]) + 1 +int(len(answer[n-1])/2)
answer[n][length] = 1
return answer[n]
|
