01타일_DP_백준_1904

-문제-

 

 

-문제 접근-

 

문제를 보면 지원이는 동주라는 빌런으로 인하여 00타일과 1 타일만을 사용하여 전체 길이가 N이 되는 2진 수열을 만들어야됩니다. 2진 수열을 만드는 경우의 수를 구하고 그 값을 15476으로 나눈 나머지를 출력해야 합니다.

 

1. 타일로 수열을 생각하기

 

   1-1. 수열의 길이

        "1"타일은 길이가 1이고 "00"타일은 길이가 2이며 길이가 N인 수열을 만들기 위해서는 두 개의 타일을 적절히

        배치하여 길이의 합이 N이 되어야 합니다.

 

   1-2. 경우의 수 도출

          수열의 시작점이 "1"타일일 경우와 "00"타일일 경우가 존재하며 

           "1타일" = 남은 길이 N-1

           "00"타일 = 남은 길이 N-2

           가 되며 전체 경우의 수 f(N)으로 시작점에 따른 다른 두 경우를 합쳐 점화식으로 표현하면

           f(N) = f(N-1) + f(N-2)

           가 도출이 되며 위의 형태가 피보나치 수열의 형태를 띄는 것을 알 수 있습니다.

 

// 여기서 피보나치 수열이란?

피보나치 수열(Fibonacci sequence)은 0과 1로 시작하며, 이전 두 개의 항을 더해서 다음 항을 만들어가는 수열이다.

 

 

2. 초기 조건

 

   2-1. f(1) =1

         길이가 1인 수열은 "1" 타일만 올 수 있으므로 경우의 수는 1이 됩니다.

 

  2-2. f(2) =2

        길이가 2인 수열은 "11"과 "00" 두 가지 경우가 있으므로 경우의 수는 2가 됩니다.

 

 

// 15746 ?

모듈러 연산 적용을 말하며 점화식의 덧셈 과정에서 값이 매우 커질 수 있으므로 이를 방지하고자 모듈러 연산을 적용해 처리합니다.

 

-전체 코드-

 

-코드 설명-

• arr[1] = 1; arr[2] = 2;
  앞서 설명한 초기 조건을 설정합니다.

 

 

• for(int i = 3; i <= n; i++) :
  길이 3부터 n까지 각 경우의 수를 점화식을 사용해 계산합니다.

 

• arr[i] = (arr[i-1] + arr[i-2]) % 15746;:
  길이 i인 수열을 만드는 경우의 수는, i-1 길이 수열 뒤에 "1" 타일을 붙이는 경우와
  i-2 길이 수열 뒤에 "00" 타일을 붙이는 경우의 합이며
  매 단계마다 모듈러 연산을 적용하여 값이 15746 미만이 되도록 합니다.

 

 

 

 

-END-

지향하는 삶