Baekjoon 9461 파도반 수열 JAVA

https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%209461

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

 

해당 문제는 아래 그림처럼 삼각형이 나선 모양으로 만들어질 때,

각 삼각형의 변의 길이를 가질 때, N 번째 삼각형의 변의 길이를 출력하는 문제다.

​

문제를 보다 말자 DP가 떠올랐고 해당 그림을 나열해보면,

1, 1, 1, 2 ,2 ,3 ,4 ,5, 7 ,9인데

첫 번째 2는 첫 번째 1 + 두 번째 1

두 번째 2는 두 번째 1 + 세 번째 1

3은 세 번째 1 + 첫 번째 2 인 것을 알 수 있다.

식으로 변환하면 dp[N] = pd[N-3] + dp[N-2]이다.

​

추가로 해당 문제는 배열을 long형으로 선언해 주었다 처음에 int로 하고 제출하니 틀렸다고 나왔고

100을 입력해보니 음수 값이 나오는 것을 확인해 수정해 주었다.