문제 링크
↓ ↓ ↓
https://school.programmers.co.kr/learn/courses/30/lessons/12900
세로 길이가 2이고, 가로길이가 n으로 주어진다.
타일은 2가지 방식 중 하나로만 배치할 수 있다.
1. (1x2) 타일을 가로로 배치하는 경우
2. (2x1) 타일을 세로로 배치하는 경우
가로길이가 n일 때 나올 수 있는 경우의 수를
1,000,000,007로 나눈 나머지를 구하는 문제
문제 핵심 및 풀이
일단 답을 구할 때 1,000,000,007로 나누라고 한 거 보니
경우의 수가 엄청나게 많이 나올 것이라는 것을 예측할 수 있다.
가로( n)가 1일 때부터 나올 수 있는 패턴을 나열해 보자.
1,2,3,5 순으로 개수가 많아진다.
답을 구할 때 1,000,000,007로 나누라고 한걸 보면,
분명히 N개의 블록을 가지고 일일이 구현해야 하는 것은 아닐 것이다.
즉, 뭔가 개수가 늘어날 때마다 답을 구할 수 있는 규칙이 있을 것이다.
이를 알아내기 위해서 표본이 많은 N = 3 일 때와 N = 4 일 때를 비교한다.
N = 4 일 때 주황색으로 칠해진 블록에는 공통점이 있다.
모두 N = 3 일 때의 모양에 세로 타일을 하나 붙인 것이다.
즉, N = 3 일 때의 개수가 무조건 N = 4 일 때 포함되어 있다.
그럼 저기서 N = 3 일 때의 모양으론 나타낼 수 없는 (완전히 초록색) 이건 어떻게 이해해야 할까?
n = 3 일 때 모양 그대로에서 타일 하나를 추가해서
맨 뒤에 해당 모양을 만드는 것은 불가능하다.
해당 모양을 어디서 찾을 순 없을 것 같다.
그런데 다행인 것은 위 그림처럼 끝에 두 블록이 누워있는 것만 N = 3 일 때의 포함되지 않는다.
그래서 이를 고유한 모양으로 보고 앞에 걸 바꿔본다고 하자.
앞에는 이제 n = 2 일 때가 비었다.
그런데 우린 이미 2x2 일 때 나올 수 있는 경우의 수를 안다.
N = 2 일 때의 나올 수 있는 모양에다가 가로로 누워있는 2x2를 붙인 것이다.
이제 N = 4 일 때의 모양이 전부 어디서 왔는지 알 수 있다.
N = 4 일 때의 나올 수 있는 경우의 수를 DP [4]라고 하자.
그럼 DP [4] = DP [3] + DP [2] → 3 + 2 = 5가 될 것이다.
이를 일반화해 본다면
DP [N] = DP [N-1] + DP [N-2]가 된다.
근데 아직 이게 확실한지 알 수가 없으니까, N = 5 일 때를 한번 구해보자.
우선 위에서 했던 것처럼, N = 4 일 때 나올 수 있는 모양에 세로 타일을 하나씩 붙인다.
총 5개가 나오게 된다.
이제 DP [N-2] 부분을 구하기 위해 N = 3으로 나올 수 있는 형태에서 가로로 누워있는 2x2를 붙여보자.
이제 여기서 N = 5 일 때 더 나올 수 있는 모양이 있는지 생각해 보자.
아무리 봐도 없다.
즉 DP [5] = DP [4] + DP [3] = 5 + 3 = 8 이 성립한다.
이로써 DP [N] = DP [N-1] + DP [N-2]가 성립함을 알았다.
이제 이를 이용하여 코드를 작성하면 된다.
코드 구현
C++ 구현 코드
↓
#include <string>
#include <vector>
using namespace std;
int solution(int n) {
int dp[60001]; // 가로가 n 일때의 경우의 수를 담는 배열
// 1과 2는 임의로 초기화
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n ;i++){
// 바텀-업 방식으로 점화식 전개
dp[i] = (dp[i-1] + dp[i-2])%1000000007;
}
int answer = dp[n];
return answer;
}↑
Java 구현 코드
↓
class Solution {
public int solution(int n) {
int[] dp = new int[60001]; // 가로가 n일 때의 경우의 수를 저장하는 배열
// n = 1, 2 일때는 임의로 초기화
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++){
// 점화식대로 식을 세우고, 1,000,000,007을 나눔
dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
}
int answer = dp[n]; // 구하고자 하는 길이 n이 저장된 dp를 가져옴
return answer;
}
}↑
시행착오
예전에 이 문제를 풀기 전에 인터넷 강의로 해당 문제 풀이를 봤었는데, 그때는 다 이해했다고 생각하고 넘어갔다.
근데 오랜만에 다시 풀어보니, 문제를 제대로 이해하지 못한 것 같다.
이 문제를 다시 풀어보기를 잘한 것 같다.
생활비..