챕터3-7. DP | 문제 풀이2 - (1) 백준 No.2193 : 이친수

이친수 문제

- https://www.acmicpc.net/problem/2193

문제요약

2진수에서 다음 두 조건을 만족하면 이친수라고 한다.
1) 0으로 시작하지 않는다.

2) 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열을 갖지 않는다.
위의 조건을 만족하는 N자리 이친수를 구하는 문제

해결 방법1 (1차원 배열)

* 기존에 해오던 방법과 새로운 방법이 있는데 두 번째의 새로운 방법이 더욱 와닿는 방법이라고 할 수 있다.

 

1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다.
- D[N] = "N자리 이친수의 개수"

 

2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다.
- 마지막 조합에서 아래와 같은 방법 중 1가지를 선택할 수 있다.

 

case1) N번째 자리에 0이 오는 이친수의 경우
=> N-1 번째에는 0, 1 모두 올 수 있다.
=> 맨 뒤가 0으로 고정되었다 생각하면 D[N-1]

 

case2) N번째 자리에 1이 오는 이친수의 경우

=> 이친수 조건을 만족해야 하기 때문에 N-1 번째에는 0만 올 수 있다. 그렇기 때문에 맨 뒤를 01로 고정시키는데 그러면
=> N-2번째에는 0, 1 모두 올 수 있다.
=> 맨 뒤가 01로 고정되었다고 생각하면 D[N-2]

 

따라서, 점화식은 D[N] = D[N-1] + D[N-2] 가 된다.

 

3. 다이나믹 프로그래밍 방법을 적용할 수 있는 문제인지 확인 => 1, 2번을 거쳐야 이게 잘 보임.
- 위와 같이 큰 문제를 작은 문제로 쪼갤 수 있으며, 작은 문제도 큰 문제와 같은 방법으로 풀 수 있고, 작은 문제들이 겹친다.
   (Overlapping SubProblem)
- 문제의 정답을 작은 문제의 정답으로부터 구할 수 있으며, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
   (Optimal Substructure)

 

4. 코드구현

<Top-down 방식>

(1) 구현
-> '재귀호출' 방식으로 구현

#include <iostream>

using namespace std;

long long d[91] = {0};

long long getTwoChinNum(int n)
{
    if ( n <= 2)
        return 1;

    else if (d[n] > 0)
        return d[n];

    else 
        d[n] = getTwoChinNum(n-1) + getTwoChinNum(n-2);
        return d[n];
}

int main()
{
    int n;
    cin >> n;
    
    d[1] = 1;
    d[2] = 1;
    
    cout << getTwoChinNum(n);
}

 

(2)시간복잡도
= 배열에 채워 넣어야하는 값의수 x 1칸을 채우는 복잡도
= N * 1 = O(N)

<Bottom-up 방식>

(1) 구현
-> 'for문을 이용한 반복문'으로 구현

#include <iostream>

using namespace std;

long long d[91] = {0};

int main() {
    int n;
    cin >> n;
    
    d[1] = 1;
    d[2] = 1;
    
    for (int i=3; i<=n; i++)
        d[i] = d[i-1] + d[i-2];

    cout << d[n] << '\n';
}

 

(2) 시간복잡도
= for 문의 반복 횟수  
= O(N)

해결 방법2 (2차원 배열)

1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다.
- D[N][L] = "마지막 자리가 L이고 길이가 N인 이친수의 개수" 라고 한다면 N자리일 때 L에 0과 1이 올 수 있다.
   D[N][0] = "마지막 자리가 0이고 길이가 N인 이친수의 개수"

   D[N][1] = "마지막 자리가 1이고 길이가 N인 이친수의 개수"
   D[N][L] = D[N][0] + D[N][1]

 

2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다.
- 정수 N이 주어지고, 앞에 어떤 조합이 존재하고 마지막 조합에서 아래와 같은 방법 중 1가지를 선택할 수 있다.

 

case1) N번째 자리에 0이 오는 이친수의 경우

=> N-1 번째에는 0, 1 모두 올 수 있다.
=> D[N][0] = D[N-1][0] + D[N-1][1]

case2) N번째 자리에 1이 오는 이친수의 경우

=> 이친수 조건을 만족해야 하기 때문에 N-1 번째에는 0만 올 수 있다.

=> D[N][1] = D[N-1][0]

 

따라서, 점화식은 D[N][0] = D[N-1][0] + D[N-1][1], D[N][1] = D[N-1][0]가 된다.
결과값을 출력할 때는 D[N][0] + D[N][1]의 결과를 출력해주면 된다.

 

3. 다이나믹 프로그래밍 방법을 적용할 수 있는 문제인지 확인 => 1, 2번을 거쳐야 이게 잘 보임.
- 위와 같이 큰 문제를 작은 문제로 쪼갤 수 있으며, 작은 문제도 큰 문제와 같은 방법으로 풀 수 있고, 작은 문제들이 겹친다.
   (Overlapping SubProblem)
- 문제의 정답을 작은 문제의 정답으로부터 구할 수 있으며, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
   (Optimal Substructure)

 

4. 코드구현
- 점화식을 사용하기 위해서는 점화식이 언제부터 성립하는지 알아야한다.
   D[N][0] = D[N-1][0] + D[N-1][1] 이라고 했던 이유는 N자리일 때 맨 뒤에 0이 오고 그 다음 0 과 1 모두 올 수 있었기 때문이다.
   그러면 이는 N=3일 때 부터 성립할 수 있다는 것을 알아야 한다.   
   N <= 2 일땐 그냥 결과값으로 1을 고정 출력으로 내보내주고, N >= 3 부터 점화식을 적용시킬 수 있는 것이다.
   즉, for문을 N >= 3 부터 적용시켜라.
   그리고 N = 3일 때 점화식이 정상적으로 작동하도록 d[2][0]의 의미와 상관없이 초기화 할 때 1 값을 주어라.
- N의 최대값을 넣어봤을 때 출력이 이상했는데 이는 오버플로우가 발생해서 그런 것이었다. D배열의 타입을 long long 으로 해주자.

<Top-down 방식>

(1) 구현
-> '재귀호출' 방식으로 구현

D의 인자가 2개이상인 경우에는 Bottom-up 방식의 구현 방법이 훨씬 쉽다.
검색해보니 대부분의 사람들도 Bottom-up 방식을 사용하여 해결하였음.

(2)시간복잡도
= 배열에 채워 넣어야하는 값의수 x 1칸을 채우는 복잡도

<Bottom-up 방식>

(1) 구현
-> 'for문을 이용한 반복문'으로 구현

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;

    long long d[91][2] = {{0, 0}, {0, 0}, {1, 0}};

    if (n <= 2)
        cout << 1 << "\n";

    else
    {
        for (int i = 3; i <= n; i++)
        {
            d[i][0] = d[i-1][0] + d[i-1][1];
            d[i][1] = d[i-1][0];
        }

        cout << d[n][0] + d[n][1] << "\n";
    }
}

(2) 시간복잡도
= for 문의 반복 횟수 
= O(N)