[BOJ] 백준 1904 01타일 / 동적 계획법(Dynamic-Programming)

이미지를 클릭하면 문제 사이트로 이동합니다.

---

 

 

💣 문제 이해

 

 

앞에 풀었던 2193번 이친수 와 상당히 비슷한 문제이다.

 

1. 0 과 1 로 이진수를 만들고자 한다.

2. 0 은 무조건 00 형태로만 쓰이고 1 은 원하는 대로 쓸 수 있다.

3. 입력으로 주어진 N 자리 수의 이진수를 총 몇 가지 만들 수 있는지 구하면 된다.

4. !! 찾은 수열의 개수를 15746 으로 나눈 나머지를 출력해야 한다 !!

 

동적 계획법(Dynamic Programming) 방식을 사용했다.

 

 

 

💭 풀이 과정

 

 

N = 1 인 경우 1 로 총 1가지

 

N = 2 인 경우 11, 00 으로 총 2가지

 

N = 3 인 경우 111, 100, 001 으로 총 3가지

 

N = 4 인 경우 1111, 1001, 1100, 0011, 0000 으로 총 5가지

 

N = 5 인 경우 11111, 11100, 10011, 11001, 00111, 00100, 10000, 00001 으로 총 8가지

 

 

경우의 수가 피보나치 수열로 변하는 것을 찾을 수 있었다.

 

 

작성 언어: C++

 

#include <cstdio>

int dp[1000010] = {0, };

void solve(int num){
    dp[1] = 1;  dp[2] = 2;
    for (int i = 3; i <= num; ++i) {
    	// 값이 지나치게 큰 경우를 대비해서 15746으로 나눈 나머지를 저장
        dp[i] = ( dp[i-2] + dp[i-1] ) % 15746;
    }
}

int main(){
    int nLength;
    scanf("%d", &nLength);
    solve(nLength);
    printf("%d\n", dp[nLength]);
    return 0;
}

 

 

 

🏆 배운 점

 

바로 앞에 풀어본 문제와 유형이 유사해서 무난하게 풀었던 문제이다.