점화식 구하기

다이나믹 알고리즘 유형의 경우 점화식을 구하는 것이 중요하다.

점화식을 구하는 방법은 n이 1일때부터 하나씩 값을 구해보며 규칙을 찾으면 된다.

위의 그림을 토대로 점화식을 구하면

d[i][1] = d[i-1][2]+d[i-1][3]

d[i][2] = d[i-2][1]+d[i-2][3]

d[i][3] = d[i-3][1]+d[i-3][2]

이 된다.

점화식을 토대로 코드를 짜면

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class _123더하기5_15990{
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringBuffer sb = new StringBuffer();
		
		int[][] d = new int[100001][4];
		d[1][1] = 1;
		d[2][2] = 1;
		d[3][1] = 1;
		d[3][2] = 1;
		d[3][3] = 1;
		
		for(int i = 4; i<d.length; i++) {
			d[i][1] =( d[i-1][2]+d[i-1][3]);
			d[i][2] = (d[i-2][3]+d[i-2][1]);
			d[i][3] = (d[i-3][1]+d[i-3][2]);
		}
		while(n-->0) {
			int num = Integer.parseInt(br.readLine());
			sb.append((d[num][1]+d[num][2]+d[num][3])%1000000009+"\\n");
		}
		System.out.println(sb);
	}
	
}

위의 코드에서 잘못된 점은 두가지다

배열 d의 자료형이 int인 것과 배열에 값을 넣어줄때 %1000000009를 해주어야 한다는 것이다.

이유는 int배열은 나머지 연산 수행 후에도 스택오버플로우를 일으키므로 long으로 바꿔줘야한다.

long으로 바꿔준 후에도 나머지 연산을 시켜줘야만 스택 오버플로우를 일으키지 않는다.

수정한 코드다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class _123더하기5_15990{
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringBuffer sb = new StringBuffer();
		
		long[][] d = new long[100001][4];
		d[1][1] = 1;
		d[2][2] = 1;
		d[3][1] = 1;
		d[3][2] = 1;
		d[3][3] = 1;
		
		for(int i = 4; i<d.length; i++) {
			d[i][1] =( d[i-1][2]+d[i-1][3])%1000000009;
			d[i][2] = (d[i-2][3]+d[i-2][1])%1000000009;
			d[i][3] = (d[i-3][1]+d[i-3][2])%1000000009;
		}
		while(n-->0) {
			int num = Integer.parseInt(br.readLine());
			sb.append((d[num][1]+d[num][2]+d[num][3])%1000000009+"\\n");
		}
		System.out.println(sb);
	}
	
}

구글링을 통해 답을 찾아서 마지막 결과값을 도출할 때 한번 더 나머지 연산을 시켜주는 이유는 모르겠다. 이유를 아는 분이 있다면 알려주시기를…