문제
9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 �
www.acmicpc.net
코드
n==1일 때 부터 5까지는 예외이다. → 따로 Basic case인 걸로 했다.
그 이후 점화식은 D(n) = D(n-1) + D(n-5) 이다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
class Main{
static long[] dp_arr = new long[101];
public static long padovan(int n) {
if(n==1 || n==2 || n==3)
return 1;
if(n==4 || n==5)
return 2;
if(dp_arr[n]!=0)
return dp_arr[n];
return dp_arr[n]=padovan(n-1)+padovan(n-5);
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine());
for(int i=0; i<t; i++)
{
int n = Integer.parseInt(br.readLine());
sb.append(padovan(n)+"\n");
}
bw.write(new String(sb));
bw.flush();
}
}
'Preparing Coding Test > Baekjoon' 카테고리의 다른 글
[Java/백준/DP] 1932번: 정수 삼각형 (0) | 2020.10.04 |
---|---|
[Java/백준/DP] 1149번: RGB거리 (0) | 2020.10.02 |
[Java/백준/DP] 1904번: 01타일 (0) | 2020.10.01 |
[Java/백준/DP] 1003번: 피보나치 함수 (0) | 2020.09.30 |
[Java/백준/DP] 2748번: 피보나치 수 2 (0) | 2020.09.25 |