[DP] 타일링 문제 11726, 11727, 9095

• 11726

DP 문제는 n에 따라 작은 수부터 직접 대입해보고 점화식을 세우는게 푸는 방법인 것 같다.

 

n이 0 또는 1이라면 1개의 경우의 수가 생기며

 

n이 2면 1*2 2*1 의 타일이 두개씩 들어가는 경우의 수가 있으므로 그 수는 2가 된다.

 

n이 3인 경우 추가로 오른쪽에 타일이 붙는다고하면

n=1인 경우에서 2*1인 타일이 가로로 두개가 오른쪽에 붙을 수 있다.

n=2인 경우에서는 1*2인 타일이 세로로 하나가 오른쪽에 붙을 수 있다. 

따라서 n=1 인 경우의 수와 n=2 인 경우의 수를 더하면 된다.

 

Bottomup 방식

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();

		int d[] = new int[n+1];
		d[0] = d[1] = 1;
		
		for(int i = 2; i <= n; i++) {
			d[i] = d[i-1] + d[i-2];
			d[i] %= 10007;
		}
		
		System.out.println(d[n]);
	}
}

Topdown 방식

public class Main {
	static int d[];
	
	static int topDown(int n) {
		if(n == 0 || n == 1) return 1;
		if(d[n] > 0) return d[n];
		
		d[n] = topDown(n-1) + topDown(n-2);
		d[n] %= 10007;
		
		return d[n];
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();
		d = new int[n+1];
		
		System.out.println(topDown(n));
	}
}

 

• 11727

위 문제에서 2*2타일이 추가되어서 1*2, 2*1, 2*2 세개 타일로 문제는 푼다.

n인 경우

n-2 인 경우에 2*1과 2*2 타일이 오른쪽에 붙는 것을 생각하고

n-1 인 경우에 1*2의 타일이 오른쪽에 붙는 것을 생각하면 된다.

 

Topdown 방식

public class Main {
	static int d[];
	
	static int topDown(int n) {
		if(n == 0 || n == 1) return 1;
		if(d[n] > 0) return d[n];
		
		d[n] = topDown(n-1) + 2*topDown(n-2);
		d[n] %= 10007;
		
		return d[n];
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();
		d = new int[n+1];
		System.out.println(topDown(n));
	}
}

 

• 9095

타일링 문제를 먼저 접하고 본 문제를 보아서 그런지 점화식으로 풀 생각으로 접근했다.

n인 경우를 볼때

n-3 의 경우에는 오른쪽에 3을 더한다고 생각하고

n-2 의 경우에는 오른쪽에 2를 더한다고 생각하고

n-1 의 경우에는 오른쪽에 1을 더한다고 생각한다

그래서 n-3, n-2, n-1 의 경우를 모두 더한 것이 n의 경우의 수가 된다.

 

public class Main {
	static int d[];
	
	static int topDown(int n) {
		if(n == 0 || n == 1) return 1;
		if(n == 2) return 2;
		if(n == 3) return 4;
		if(d[n] > 0) return d[n];	
		d[n] = topDown(n-1) + topDown(n-2) + topDown(n-3);
		
		return d[n];
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		d = new int[11];

		for(int i = 0; i < n; i++) {
			int a = sc.nextInt();
			System.out.println(topDown(a));
		}
		sc.close();
	}
}