[JAVA] BOJ 9461 파도반 수열

 

동적 계획법(DP) 문제이다 보니 조금 난이도가 있었다. 파도반 수열을 쭉 써보면 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37.... 이렇게 이어지는 것을 알 수 있다. 동적 계획법은 수열의 패턴, 즉 점화식을 찾아내는 것이 가장 먼저이기 때문에 패턴을 분석해보니 6번째 숫자부터 f(N) = f(N-1)+ f(N-5)를 따르고 있었다.

 

static long padovan(int N) {
		if (N_li[N]==0) return N_li[N] = (padovan(N-1) + padovan(N-5));
		return N_li[N];
	}

 

이런 식으로 재귀 함수를 구성해주면 되고 N_li라는 배열은 메모 이제이 션(Memoization)을 구현하기 위해 만들어준 배열이다.

 

public static long[] N_li = new long[101];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		N_li[1]=1;
		N_li[2]=1;
		N_li[3]=1;
		N_li[4]=2;
		N_li[5]=2;
		StringTokenizer st;
		for (int i=0; i<N;i++) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			bw.write(String.valueOf(padovan(n)));
			bw.newLine();
		}
		//System.out.println(Arrays.toString(N_li));
		bw.flush();
		bw.close();
	}
	static long padovan(int N) {
		if (N_li[N]==0) return N_li[N] = (padovan(N-1) + padovan(N-5));
		return N_li[N];
	}

 

전체 코드를 보면 입출력에는 시간을 단축하기 위해 BufferedReader와 BufferedWriter를 사용했고, 파도반 수열이 5번째까지는 특정한 패턴이 없다 보니 초기값을 저장해주었다. 

 

*N_li 배열의 데이터타입을 int로 하지 않은 이유는 N의 범위가 1과 100 사이의 값인데 N의 값이 커지면서 int의 범위 (-2,147,483,648 ~ 2,147,483,647)를 넘어서게 되고 이로 인해 엉뚱한 값이 나오기 때문이다. 

보다시피

[0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, 351, 465, 616, 816, 1081, 1432, 1897, 2513, 3329, 4410, 5842, 7739, 10252, 13581, 17991, 23833, 31572, 41824, 55405, 73396, 97229, 128801, 170625, 226030, 299426, 396655, 525456, 696081, 922111, 1221537, 1618192, 2143648, 2839729, 3761840, 4983377, 6601569, 8745217, 11584946, 15346786, 20330163, 26931732, 35676949, 47261895, 62608681, 82938844, 109870576, 145547525, 192809420, 255418101, 338356945, 448227521, 593775046, 786584466, 1042002567, 1380359512, 1828587033, 2422362079, 3208946545, 4250949112, 5631308624, 7459895657, 9882257736, 13091204281, 17342153393, 22973462017, 30433357674, 40315615410, 53406819691, 70748973084, 93722435101, 124155792775, 164471408185, 217878227876, 288627200960, 382349636061, 506505428836, 670976837021, 888855064897]

파도반 수열을 100번째까지 진행하면 마지막 수는 약 9천억에 가까운 수가 나오므로 long 타입을 선언해주었다.