[알고리즘]프로그래머스 12900번 - 2 x n 타일링

프로그래머스 12900번 - 2 x n 타일링

프로그래머스 12900번 - https://programmers.co.kr/learn/courses/30/lessons/12900

 

요구사항

1. 세로의 길이가 2이고 가로의 길이가 n인 바닥을 타일로 채우는 방법의 수를 반환하라.

2. 타일은 가로길이가 2이고 세로의 길이가 1인 직사각형 모양입니다.

 

요구사항 분석 및  풀이과정

1. 가로가 n인 바닥을 타일로 채울 수 있는 경우의 수는 마지막 타일을 세로로 배치하는 경우와 가로로 배치하는 경우로 나눌 수 있습니다.

2. 가로가 n인 바닥을 타일로 채울 수 있는 경우의 수를 dp[n]이라고 정의하면 다음과 같습니다.

 

dp[n] = dp[n-2] + dp[n-1] ( n >= 3 )

 

dp[n-2]는 마지막 타일을 가로로 배치하여 가로의 길이가 2인 타일을 위아래로 2개 배치하는 경우입니다.

dp[n-1]는 마지막 타일을 세로로 배치하여 가로의 길이가 1인 타일을 하나 배치하는 경우입니다.

 

dp[1] = 1 ( 타일을 세로로 배치하는 경우 1가지 )

dp[2] = 2 ( 타일을 가로로 배치하는 경우 2가지 )

 

소스코드 작성

class Solution {

	private static final int MOD = 1_000_000_007;

	private static int mod(int a, int b) {
		return ((a % MOD) + (b % MOD)) % MOD;
	}

	public int solution(int n) {
		int[] dp = new int[n + 1];
		dp[1] = 1;
		dp[2] = 2;

		for (int i = 3; i <= n; i++) {
			dp[i] = mod(dp[i - 1], dp[i - 2]);
		}

		return dp[n];
	}
}

 

결과

 

소스코드 깃허브 주소

링크