[프로그래머스] 3 x n 타일링 - MOD 모듈러 연산

문제

 

풀이

#include <string>
#include <vector>
#include <iostream>
using namespace std;
// mod 알고리즘
int solution(int n) {
    long long mod = 1000000007;
    vector<int> v = {0,3,11};
    if( n%2 != 0) return 0;

    for(int i=3; i<=n/2; i++){
        long long sum=0;
        sum += (v[i-1] * 3 + 2)%mod;
        for(int j=i-2; j>0; j--){
            sum += (v[j] * 2) % mod;
        }
        v.push_back(sum%mod);
    }
    
    return v[n/2]% mod;
}

 

n이 홀수일 경우는 타일을 놓을 수 있는 방법이 없다. 0을 리턴한다. 

 

f(2)의 타일을 놓을 수 있는 방법은 3가지이다.

 

f(4)는 이전의 모습에서 타일이 2개 추가되었으므로 f(이전 단계) * f(2)인데, 

f(4) 이상일 때부터는 특수한 타일 배치가 2개씩 추가되므로

f(4) = f(2)*f(2) + 2 = 11이다.

 

f(6)의 경우 위와 마찬가지로  f(이전단계) * 3 + 2인데,

f(4)였을때 나온 특수한 타일 배치법을 생각한다. 이 배치법은 두 번씩 나오기 때문에 f(6-4)*2를 해준다. 즉

f(6) = f(4)*3 + f(2)*2 + 2 = 41이다.

 

위와 같은 식으로 볼 때 f(8) = f(6)*3 + f(4)*2 + f(2)*2 +2이며

규칙성을 찾아보면

f(n) = f(n-2)*3 + f(n-2)*2 + f(-4)*2 + ... + f(2)*2 + 2 

라는 점화식을 얻을 수 있다.

 

MOD - 모듈러 연산 (나머지 연산)

알고리즘 문제 중에서 구한 값의 나머지를 구해야 하는 경우가 있는데, 구한 값이 int형이나 long형의 표현 가능 범위를 벗어나게 되는 경우 mod연산을 통해 크기를 줄일 수 있다.

 

표현 가능 범위

• int : -2,147,483,648~ 2,147,483,647
• long : -2,147,483,648~ 2,147,483,647
• long long : -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

 

사칙 연산에 대해 모듈러 연산은 다음이 성립한다. (나누기는 성립하지 않는다.)

 

합 분해 : (A+B) mod C = (A mod C + B mod C) mod C

(A+B)%C = (A%C + B%C)%C

 

 

뺄셈 분해 : (A-B) mod C = (A mod C - B mod C) mod C

(A-B) %C = (A %C - B %C) %C

 

 

곱 분해 : (A*B) mod C = ((A mod C) * (B mod C)) mod C

(A*B) %C = ((A %C) * (B %C)) %C

 

 

---

다른 사람 풀이

#include <string>
#include <vector>
#define MOD 1000000007

using namespace std;

long long arr[5001];

int solution(int n) {
    int answer = 0;
    if(n % 2 != 0)
        return 0;
    arr[0] = 1;
    arr[2] = 3;
    
    for(int i = 4 ; i <= n ; i+=2){
        arr[i] = (arr[i-2] * 3);
        for(int j = 0 ; j <= i-4 ; j += 2){
            arr[i] += (arr[j] * 2) % MOD;
        }
        arr[i] %= MOD;
    }
      
    answer = arr[n] % MOD;
    return answer;
}

 

---

https://velog.io/@kekim20/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%82%98%EB%A8%B8%EC%A7%80%EC%97%B0%EC%82%B0Modular-Arithmetic-mod

[알고리즘] 나머지연산(Modular Arithmetic : mod)

https://s2choco.tistory.com/24

프로그래머스 - 3xn 타일링 풀이 (python3)