코딩 테스트/프로그래머스
[프로그래머스][Level3][2 x n 타일링]
갓생사는 김초원의 개발 블로그
2020. 11. 26. 00:25
[문제 설명]
https://programmers.co.kr/learn/courses/30/lessons/12900
코딩테스트 연습 - 2 x n 타일링
가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는
programmers.co.kr
[풀이 과정]
[Java DP] 프로그래머스 2 X n 타일링
Dynamic Programming의 대표적인 문제인 2XN 타일링 문제입니다. 문제 DP문제는 케이스를 나누는 것이 중요합니다. 케이스를 나눌 때는 문제를 다 풀기 직전의 상황부터 거꾸로 푸는 방법이 좋습니다.
deveric.tistory.com
- DP 문제는 케이스를 나누는 것이 중요!
- 문제를 다 풀기 직전의 상황을 이용하여 거꾸로 푸는 방법이 좋음!
[JAVA code]
package com.algorithm.programmers.level3;
public class Test02 {
public static void main(String[] args) {
System.out.println(solution(4));
}
public static int solution(int n) {
int answer = 0;
int[] nArray = new int[n + 1];
nArray[1] = 1;
nArray[2] = 2;
for (int i = 3; i < n + 1; i++) {
nArray[i] = (nArray[i - 2] + nArray[i - 1]) % 1000000007;
}
answer = nArray[n];
return answer;
}
}