백준
백준 9461번 : 파도반 수열
Huiyeong
2021. 3. 19. 02:37
문제
9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의
www.acmicpc.net
구현 방법
점화식을 구해준 다음 dp로 구현하였습니다.
그림을 보면 점화식은 dp[i] = dp[i-2] + dp[i-3] 임을 알 수 있습니다.
구현 코드
package BOJ.Silver;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BOJ9461_파도반수열 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int TC = Integer.parseInt(br.readLine());
for (int tc=0;tc<TC;tc++) {
int N = Integer.parseInt(br.readLine());
long[] dp = new long[N+1];
dp[1]=1;
if (N>1) dp[2]=1;
if (N>2) dp[3]=1;
for (int i=4;i<=N;i++) {
dp[i] = dp[i-2]+dp[i-3];
}
sb.append(dp[N]+"\n");
}
System.out.println(sb);
}
}
