9461번 파도반 수열 문제를 풀어보았다.
9461 파도반 수열
https://www.acmicpc.net/problem/9461
9461번: 파도반 수열
문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하
www.acmicpc.net
이 문제는 파도반 수열의 n번째 수를 구하는 문제이다.
그래서 파도반 수열이란 첫 삼각형을 정삼각형으로 변의 길이는 1, 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가하는 수열이다.
나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.
그래서 이런 식으로 1 1 1 2 2 3 4 5 7 9 12 16 21 ... 수열을 띈다.
우선 잠시 관찰을 해본 나는 P(n)=P(n-3)+P(n-2) 라는 점화식을 세울 수 있었다.
그런식으로 만드려고보니 제한 시간 1초가 넘을 것 같았다.
왜냐하면 범위가 100인데 피보나치도 그렇게하면 1초를 넘긴다.(근데 이거 피보나치랑 별로 다를게 없는데)
여튼 그래서 배열에 저장을 해가면서 풀어보았다.
...풀고나니 틀렸다.
정신을 차리고 100을 넣어봤더니 정수범위를 아득하게 뚫고 나갔다.
그래서 long long int 로 처리를 해주어서 풀었다.
#include <stdio.h>
long long int memme[102]={0};
long long int P(int x) {
if(memme[x]) return memme[x];
return memme[x]=P(x-3)+P(x-2);
}
int main()
{
int i,t,n;
scanf("%d", &t);
memme[1]=1;
memme[2]=1;
memme[3]=1;
for(i=0; i<t; i++) {
scanf("%d", &n);
printf("%lld\n",P(n));
}
}