[BOJ 15990] 123더하기 5 (java)

문제 링크 https://www.acmicpc.net/problem/15990

저번에 풀었던 123 더하기에 같은 수를 두 번 이상 연속해서 사용하면 안 된다. 라는 조건이 붙은 문제이다.

그래서 memo[n] = memo[n-1]+memo[n-2]+memo[n-3] 점화식으로만은 풀 수 없는 문제였고,

2차원 배열을 사용해서 마지막 자리 수를 고정시켜놨을때 올 수 있는 조건을 처리해줬어야 했다.

memo[n][k] : k가 마지막 자리 수 일때, n을 1,2,3으로 만드는 방법 

Ex) 5를 같은 수를 두번 이상 연속해서 사용하지 않고 1,2,3 을 더해 만들 수 있는 경우의 수

// 어떤수 + 1 = 5 , 어떤수는 4 가 되고 연속해서 같은 수가 올 수 없으니까 1과 다른 수인 2, 3 이 올 수 있다.  
memo[5][1] = memo[4][2] + memo[4][3] 
// 어떤수 + 2 = 5 , 어떤수는 3이 되고 연속해서 같은 수가 올 수 없으니까 2와 다른 수인 1 , 3 이 올 수 있다.
memo[5][2] = memo[3][1] + memo[3][3]
memo[5][3] = memo[2][1] + memo[2][1] 

구한 세가지의 경우의 수를 더해주면 값이 나온다.

Bottom-up 문제풀이

package basics_400;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ15990 {
	// memo[n][k] : k가 마지막 자리 수 일때, n을 1,2,3으로 만드는 방법 
	static int[][] memo =new int[100001][4] ;
	static void make123_5() {

		//초기화
		memo[1][1] = memo[2][2] = memo[3][3] = memo[3][1] = memo[3][2] = 1;

		// n=3까지는 초기화를 해줬기 때문에 4부터 시작
		for (int i = 4; i <= 100000; i++) {
			// 마지막 자리수에 1,2,3 을 넣으면서 올 수 있는 경우를 다르게한뒤 계산 
			memo[i][1] = (memo[i - 1][2] + memo[i - 1][3]) % 1000000009;
			memo[i][2] = (memo[i - 2][1] + memo[i - 2][3]) % 1000000009;
			memo[i][3] = (memo[i - 3][1] + memo[i - 3][2]) % 1000000009;

		}
	}

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		// 테스트케이스
		make123_5();
		//미리 memo에 답을 구해놨기 때문에 n만 바꿔서 출력해주면 됨 
		int tc = Integer.parseInt(br.readLine());
		while (tc-- > 0) {
			// tc만큼 n입력
			int sum = 0;
			int n = Integer.parseInt(br.readLine());
			sum += memo[n][1];
			sum %= 1000000009;
			sum += memo[n][2];
			sum %= 1000000009;
			sum += memo[n][3];
			sum %= 1000000009;
			sb.append(sum + "\n");

		}
		System.out.println(sb);

	}

}