공부공간

프로그래머스 ) 종이접기 본문

알고리즘/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]
      
  

 

 

 

'알고리즘 > Dynamic Programming' 카테고리의 다른 글

BOJ - 11052) 카드 구매하기  (0) 2020.01.29
BOJ - 10164 ) 격자상의 경로  (0) 2020.01.27
BOJ - 1003 ) 피보나치 함수  (0) 2020.01.07
BOJ - 11054) 가장 긴 바이토닉 부분 수열  (0) 2020.01.06
BOJ - 11055) 가장 큰 증가 부분 수열  (0) 2020.01.06
'알고리즘/Dynamic Programming' Related Articles more
Comments