Baekjoon - 15988

문제

Solved.ac Silver2

접근 방식

계산을 하다 보니 n = (n-1)+(n-2)+(n-3) 임을 발견하였다.

1차시도

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int testCaseSize = Integer.parseInt(br.readLine());
		for (int i = 0; i < testCaseSize; i++) {
			int targetNumber = Integer.parseInt(br.readLine());
			int[] dp = new int[targetNumber + 1];
			dp[1] = 1;
			if (targetNumber >= 2) {
				dp[2] = 2;
			}
			if (targetNumber >= 3) {
				dp[3] = 4;
			}
			for (int j = 4; j < targetNumber + 1; j++) {
				dp[j] = dp[j - 1] + dp[j - 2] + dp[j - 3];
			}
			sb.append(dp[targetNumber]).append("\n");
		}
		System.out.println(sb);
	}
}

실패

2~4차시도

1000000009 로 나누지 않은걸 발견하여 여러 시도를 했으나 실패

5차시도

더할 때 자료형의 int 범위를 넘어감을 발견

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int testCaseSize = Integer.parseInt(br.readLine());
		for (int i = 0; i < testCaseSize; i++) {
			int targetNumber = Integer.parseInt(br.readLine());
			long[] dp = new long[targetNumber + 1];
			dp[1] = 1;
			if (targetNumber >= 2) {
				dp[2] = 2;
			}
			if (targetNumber >= 3) {
				dp[3] = 4;
			}
			for (int j = 4; j < targetNumber + 1; j++) {
				dp[j] = (dp[j - 1] + dp[j - 2] + dp[j - 3]) % 1000000009;
			}
			sb.append(dp[targetNumber]).append("\n");
		}
		System.out.println(sb);
	}
}

성공

추가시도

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int testCaseSize = Integer.parseInt(br.readLine());
		for (int i = 0; i < testCaseSize; i++) {
			int targetNumber = Integer.parseInt(br.readLine());
			int[] dp = new int[targetNumber + 1];
			dp[1] = 1;
			if (targetNumber >= 2) {
				dp[2] = 2;
			}
			if (targetNumber >= 3) {
				dp[3] = 4;
			}
			for (int j = 4; j < targetNumber + 1; j++) {
				dp[j] = (int)(((long)dp[j - 1] + (long)dp[j - 2] + (long)dp[j - 3]) % (long)1000000009);
			}
			sb.append(dp[targetNumber]).append("\n");
		}
		System.out.println(sb);
	}
}

1000000009 의 범위는 int 내부이니까 long으로 타입 변환 후 계산하는 방식으로 해결

성능은 int 쓰는게 메모리와 시간 다 적게쓰는걸로