728x90
반응형
문제:
위 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.
파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1,1,1,2,2,3,4,5,7,9이다.
N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1<=N<=100)
출력:
각 테스트 케이스마다 P(N)을 출력한다.
풀이 방법:
수열 문제이므로 규칙을 찾는 것이 가장 중요하다. 파도반 수열은 다음과 같은 규칙을 가지고 있다.
P(N)=P(N-2)+P(N-3)
따라서 이를 처음에는 피보나치와 같이 재귀적 방법으로 풀려고 했으나 시간초과가 발생하게 되었다. 그래서 미리 길이 N의 배열을 만들어 놓고 반복문으로 배열의 인덱스를 참조하며 P(N)을 구하였다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | for i in range(int(input())): number=int(input()) answer=[0]*(number+1) if number==1 or number==2 or number==3: print(1) elif number==4: print(2) else: answer[1]=1 answer[2]=1 answer[3]=1 answer[4]=2 for i in range(5,number+1): answer[i]=answer[i-3]+answer[i-2] print(answer[number]) | cs |
728x90
반응형
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]2193. 이친수 (0) | 2019.04.30 |
|---|---|
| [BOJ]1003. 피보나치 함수 (0) | 2019.04.26 |
| [BOJ]9095. 1,2,3 더하기 (0) | 2019.04.24 |
| [BOJ]11052. 카드 구매하기 (0) | 2019.04.23 |
| [BOJ]10844. 쉬운 계단 수 (0) | 2019.04.22 |