글 읽기 - 11727 에서 경우의 수 제가 잘못생각하는건지?

dlfgp 7년 전 0

11727 번에서 n= 2 일때 3가지인 것으로 봐서 || (2*1 두개) 혹은 = (1*2 두개) 혹은 ㅁ (2*2 1개) 를 3가지 경우의 수로 생각한 것 같습니다.

그렇다면 풀이는

arr[1] = 1;
arr[2] = 3;

for (int i = 3; i <= n ; i++) {
arr[i] = arr[i-1] + arr[i-2]*3;
arr[i] %= 10007;
}

이렇게 되어야 할 것 같은데요

답이 틀리더라고요

맞은 답을 보니

점화식이 arr[i] = arr[i-1] + arr[i-2]*2 이던데.. 곱하기 2를 하면 안되지 않나요.

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();
		
		int arr[] = new int[n+1];
		arr[1] = 1;
		arr[2] = 3;
		
		for (int i = 3; i <= n ; i++) {
			arr[i] = arr[i-1] + arr[i-2]*3;
			arr[i] %= 10007;
			
		}
		System.out.println(arr[n]);
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

11727 에서 경우의 수 제가 잘못생각하는건지?

dlfgp 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말