[JAVA / 자바] 백준 9461번 - 파도반 수열 (실버 3)

 문제 

위 그림과 같이 삼각형이 나선 모양으로 놓여 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

---

 입력 

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

---

 출력 

각 테스트 케이스마다 P(N)을 출력한다.

---

 

---

 문제 접근 방법 

이번 문제는 다이나믹 프로그래밍(Dynamic Programming) 문제로 점화식을 찾아 코드를 짜주면 된다.

이번 점화식은 피보나치 수열과 매우 유사한 형태를 띠고 있다.

f(x) = f(x-3) + f(x-2);

따라서 f(1) ~ f(3)까지는 초기 값을 직접 입력해주어야 한다. (∵ n ≥ 1)

  ☞ f(1) = f(2) = f(3) = 1;

이후 함수를 통해 이전에 연산이 된 값이면 배열에 저장되어있으므로 바로 해당 인덱스에 저장된 값을 출력해주면 되고,

만약 연산이 되지 않은 값이면 가장 마지막에 연산된 결과부터 해당 인덱스까지 이어 계산하여 배열에 저장한 후 출력한다.

---

 JAVA 코드 풀이 

 코드 실행 결과 

---

 후기 

이번 문제는 비교적 점화식이 쉽게 보여 빠르게 풀 수 있었다.

---

 문제 원본 

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

9461번: 파도반 수열

 알고리즘 분류 

• 수학
• 다이나믹 프로그래밍