[DP] 9465, 2156

• 9465번

• 과정
  • 규칙을 보면 이친수는 0으로 시작하지 않고 1이 두번 연속으로 나타나지 않는다는 규칙이 있다.
    • n-1의 이친수가 끝자리가 0으로 끝이 나는 경우 뒤에 1이 올 수 있다.
    • n-1의 이친수가 끝자리가 0으로 끝이 나는 경우 뒤에 0 또는 1이 올 수 있다.
      • n의 이친수 끝자리가 0으로 끝나는 경우 점화식
        • dp[n][0] = dp[n-1][1] + dp[n-1][0]
      • n의 이친수 끝자리가 1로 끝나는 경우는 점화식
        • dp[n][1] = dp[n-1][0]
  • 이중배열의 경우 n행과 열의 경우의 수따라 열의 개수를 정해주어야 하는데 이전에는 숫자들이 1~9까지 이거나 개수가 많았다. 이 경우는 0과 1로 나누어 계산할 수 있으므로 열의 개수는 2개로 충분하다.

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);     
		int n = sc.nextInt();
		sc.close();
		
		long dp[][] = new long[n+1][2];
		long result = 0;
		
		dp[0][1] = 1;
		dp[1][0] = 1;
		
		for(int i = 2; i < n; i++) {
			dp[i][0] = dp[i-1][0] + dp[i-1][1];
			dp[i][1] = dp[i-1][0];
			
		}
		
		result += dp[n-1][0] + dp[n-1][1];
		
		System.out.println(result);
	}
}

 

• 9465번

public class Main {
	static int dp[][] , score[][];
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in); 
		int test = sc.nextInt();
		
		for(int i = 0; i < test; i++) {			
			int n = sc.nextInt();
		
			dp = new int[2][n+1];
			score = new int[2][n+1];
		
			for(int m = 0; m < 2; m++) {
				for(int j = 1; j <= n; j++) {
					score[m][j] = sc.nextInt();
				}
			}
			
			dp[0][1] = score[0][1];
			dp[1][1] = score[1][1];
			
			for(int k = 2; k <= n; k++) {
				dp[0][k] = Math.max(dp[1][k-1], dp[1][k-2]) + score[0][k];
				dp[1][k] = Math.max(dp[0][k-1], dp[0][k-2]) + score[1][k];
				
			}
			
			System.out.println(Math.max(dp[1][n], dp[0][n]));

		}
		
		sc.close();

	}
}