[SWEA] 3376. 파도반 수열

문제

아래 그림과 같이 삼각형이 나선모양으로 늘어서 있는 형태를 생각해보자.

아래 그림과 같이 삼각형이 나선모양으로 늘어서 있는 처음에 이 나선은 한 변의 길이가 1인 정삼각형에서 시작한다.

그리고 현재 만들어진 나선에서 가장 긴 변에 그 변의 길이와 같은 크기의 정삼각형을 추가해 넣는다. 파도반 수열 PN은 나선에 N번째로 추가한 나선의 길이를 의미하는 수열이다.

P1에서 P10까지를 순서대로 나열하면 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어질 때 PN을 구하는 프로그램을 작성하라.

 

풀이방법

파도반 수열은 대표적인 동적 계획(DP, Dynamic Programming) 알고리즘으로 해결할 수 있는 문제이다. 

 

문제에 주어진 값으로 점화식을 세우면 D[n] =  D[n-1] + D[n-5]이다. 따라서 D[5]까지만 알면 그 이후의 값은 점화식으로 찾을 수 있다. 

 

소스코드

package samsung;

import java.util.*;

public class s_3376 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			int n = sc.nextInt();
			long[] a = new long[101];
			a[1] = 1; a[2] = 1; a[3] = 1; a[4] = 2; a[5] = 2;
			
			for(int i = 6; i <= n; i++) {
				a[i] = a[i-1] + a[i-5];
			}
			System.out.println("#" + t + " " + a[n]);
		}
	}
}

 

출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWD3Y27q3QIDFAUZ&categoryId=AWD3Y27q3QIDFAUZ&categoryType=CODE

SW Expert Academy