[알고리즘][Java] 백준(BOJ) 11726 2Xn 타일링_자바

 

DP

11726 2Xn 타일링    www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

 

 

문제 풀기 전 공부할 것 : 다이나믹 프로그래밍

 

 

 

 

 

 

 

풀이

<내용>

• DP를 이용해서 해결할 수 있는 문제이다.
• Scanner를 이용하여 n값을 입력받는다.
• 2Xn 타일링의 규칙을 찾는다.
• 1일 때는 1가지 경우만 가능하다.
• 2일 때는 2가지 경우만 가능하다.
• 3일 때를 보면 1일 때에서 가로로 누은 타일 2개를 붙이는 경우와 2일 때 세로 타일 1개를 붙이는 경우가 있다.
• 따라서 n일 때는 n-2의 경우의 수 + n-1의 경우의 수이다.
• 이 규칙에 따라 for문을 반복할 것인데 n이 1 이상이므로 1은 1개로 초기화 가능하다.
• n이 2일 때도 초기화했을 경우 발생할 수 있는 오류는 n의 값이 1일 때 범위를 넘어간 배열에 초기화하는 것으로 n이 2일 때도 for문에 포함될 수 있도록 구현한다.
• 배열을 0 - n까지 n+1을 크기로 정하고 n이 2일 때도 성립하기 위해 n이 0일 때를 1로 초기화한다.
• 그리고 10,007로 나눈 나머지를 출력해야 하므로 잊지 않고 %10007을 해야 한다.
  • 이걸 안 해서 틀리는 경우가 꽤 있다.

 

 

<코드>

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[] dp = new int[n+1];
		dp[0] = 1;
		dp[1] = 1;
		for (int i=2; i<=n; i++) {
			dp[i] = (dp[i-2] + dp[i-1]) % 10007;
		}
		
		System.out.println(dp[n]);

	}

}

 

 

 

 

 

 

 

 

 

 

 

 

 

같은 문제 파이썬 풀이법

2020/03/19 - [Algorithm/백준 알고리즘_Python] - [알고리즘][Python] 백준(BOJ) 11726 2xn 타일링_파이썬

[알고리즘][Python] 백준(BOJ) 11726 2xn 타일링_파이썬