https://www.acmicpc.net/problem/9461
9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의
www.acmicpc.net
이번 문제는 동적 계획법과 피보나치 수열의 응용 버전이라고 생각하면 편하다.
이번 문제는 4번째 값부터 한칸 뒤의 두 수의 합과 같다.
즉, dp[i] = dp[i-2] + dp[i-3] 으로 표현할 수 있다.
풀이는 아래와 같다.
소스코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main
{
// N : 1 ~ 100
static long[] seq = new long[101];
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
padovan();
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++)
{
sb.append(seq[Integer.parseInt(br.readLine())]).append('\n');
}
System.out.println(sb);
}
public static void padovan()
{
seq[1] = 1;
seq[2] = 1;
seq[3] = 1;
// N : 1 ~ 100
for (int i = 4; i < 101; i++)
{
seq[i] = seq[i - 2] + seq[i - 3];
}
}
}