[BOJ] 백준 2193 이친수 / 동적 계획법(Dynamic-Programming)

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

---

 

💣 문제 이해

 

 

1. 첫 번째 자리가 1로 시작하는 수이다.

2. 1과 1이 인접할 수 없다고 했으니, 두 번째 자리는 0 이다.

3. N 자릿수 중에서 이러한 규칙을 만족하는 수의 개수를 구해야 한다.

 

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

 

 

 

💭 풀이 과정

 

 

N = 1 인 경우는 1 하나밖에 없다. => 1

 

N = 2 인 경우는 10 하나밖에 없다. => 1

 

N = 3 인 경우는 100, 101 두 가지이다. => 2

 

N = 4 인 경우는 1000, 1001, 1010 세 가지이다. => 3

 

N = 5 인 경우는 10000, 10001, 10010, 10100, 10101 다섯 가지이다. => 5

 

 

 

 

이 규칙을 토대로 발견할 수 있는 것은

 

1) 바로 앞 케이스에 따라 다음 케이스가 정해진다고 볼 수 있다.

N = 3 일 때의 100에서 뒤에 0 또는 1 을 붙일 수 있고 101 에서 뒤에 0 을 붙일 수 있다. 이것이 N = 4 일 때의 종류

 

2) 개수의 변화가 피보나치와 동일하다.

 

 

 

이 두 가지 방식으로 소스코드 작성을 해보았다.

 

 

 

<1 번 소스코드>

 

작성 언어: C++

 

#include <cstdio>

long dp[100][2] = {0, };    // 0 번째 열이 0으로 끝나는 경우, 1 번째 열이 1로 끝나는 경우

void solve(int num){
    dp[1][0] = 0; dp[1][1] = 1;
    for (int i = 2; i <= num; ++i) {
        dp[i][0] = dp[i-1][0] + dp[i-1][1];
        dp[i][1] = dp[i-1][0];
    }
}

int main(){
    int nCount = 0;
    scanf("%d", &nCount);
    
    solve(nCount);
    printf("%ld\n", dp[nCount][0] + dp[nCount][1]);
    return 0;
}

 

 

 

직접 몇 가지 케이스를 적어보다보면 발견하게 되는 규칙이 있다.

 

0 으로 끝나는 수는 그 다음 케이스에 0 으로 끝나는 수, 1 로 끝나는 수 두 가지를 만들 수 있다는 것이고,

1 로 끝나는 수는 그 다음 케이스에 0 으로 끝나는 수 한 가지만 만들 수 있다는 것이다.

 

이를 통해 점화식을 작성하면 다음과 같다.

 

dp[i][0] 은 i 자리 숫자에서 0 으로 끝나는 수의 개수이고 dp[i][1] 은 i 자리 숫자에서 1 로 끝나는 수의 개수이다.

 

dp[i][0] = dp[i-1][0] + dp[i-1][1]  =>  0 으로 끝나는 수와 1 로 끝나는 수 모두 공통적으로 0 으로 끝나는 수를 만들 수 있다.

dp[i][1] = dp[i-1][0]  => 0 으로 끝나는 수만 1 로 끝나는 수를 만들 수 있다.

 

 

 

<2 번 소스코드>

 

작성 언어: C++

 

#include <cstdio>

long dp[100] = {0, };

void solve(int num){
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= num; ++i) {
        dp[i] = dp[i-2] + dp[i-1];
    }
}

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

 

 

피보나치 방식 풀이이다.

 

 

 

🏆 배운 점

 

dp 문제 중 간단한 편에 속하는 문제이나,

두 가지 풀이로 접근할 수 있는 것을 시도해보아서 개인적으로 좀 뿌듯한 풀이였던 것 같다