[백준 11726: 2XN 타일링] kotlin 풀이 (피보나치, 팩토리얼)

접근법 1) 경우의 수, 팩토리얼 활용하기

1. n의 값을 알때 n을 (1*2)블럭 몇개와 (2 * 1)블럭 몇개로 채울것인가?

   n/2를 해서 (2*1)블럭을 k개, k-1, ... 1, 0개로 채우는 경우를 생각해볼 수 있다

2. 세로블럭 a개, 가로블럭 b개를 가지게되는 경우의 경우의 수는 이항계수를 활용할 수 있다.

   val vertical = a
   val horizontal = b

   (a + b) ! / a!*b! == aCb

   그런데 이럴 경우 n!의 결과값 까지 모두 구해야한다는 단점이 있다.

3. 나머지 정리이야기를 해보자. A+B를 m으로 나눈 나머지를 구하고자 할때, A를 m으로 나눴을때의 나머지와, B를 m으로 나눈 나머지를 더하면 A+B를 미리 더한값을 m으로 나눴을때의 나머지와 동일한 값을 도출할 수 있다. 이는 뺄셈에서도 성립한다. 그러나 본 문제에서 구해야하는 2번블록의 경우 곱셈과 나눗셈 연산을 활용하는데, 이 경우에는 나눗셈 정리를 활용할 수 없다.

4. 예를들어 n의 최대값인 1000!을 다 구하고.. 또 분모의 값을 계산해서 나누고.. 이런 계산을 하기에 우리의 컴퓨터는 아직 나약하다. 다른 방식을 생각해보자

5. 아래는 팩토리얼을 계산해 답을 도출해내는 코드이다. 그러나, 일정 수 이상으로 커지면 오버플로우가 발생하기 때문에 틀린 코드이다.

package beakjoon.dp

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.system.exitProcess

lateinit var fac: IntArray

fun getFactorial(n: Int) {
    // 최대 n까지 필요함
    fac[0] = 1
    fac[1] = 1

    for (i in 2..n) {
        fac[i] = (fac[i - 1] * i)
    }
}

fun main() {

    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    fac = IntArray(n + 1)

    if (n == 1 || n == 2) {
        println(n)
        exitProcess(0)
    }

    getFactorial(n)

    val max = n / 2
    var sum = 0

    for (horizontal in max downTo 0) {
        val vertical = n - (2 * horizontal)

        val dividend = fac[horizontal + vertical] // 분모
        val divisor = when {
            fac[horizontal] == 0 -> fac[vertical]
            fac[vertical] == 0 -> fac[horizontal]
            else -> (fac[horizontal] * fac[vertical])
        }
        val add = dividend / divisor
        sum += add

    }
    println(sum)
}

접근법 2) 피보나치 수열

• DP는 참 얼탱가리 없는 문제가 많다.
  • n=1 -> 1
  • n=2 -> 2
  • n=3 -> 3
  • n=4 -> 5
  • n=5 -> 8 (?)
• IT회사에 취업하려면.. 이 숫자만 보고 피보나치 수열임을 눈치채야 하는것일까..~?
• 피보나치 수열에 대한 점화식만 작성해주면 이항계수를 구할 필요 없이 간단하게 해결할 수 있는 문제였다고 한다.

package beakjoon.dp

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.system.exitProcess

lateinit var fac: IntArray
fun main() {

    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    fac = IntArray(n + 1)

    if (n == 1 || n == 2) {
        println(n)
        exitProcess(0)
    }


    fac[1] = 1
    fac[2] = 2

    for (i in 3..n) {
        fac[i] = (fac[i - 1] + fac[i - 2]) % 10_007
    }
    println(fac[n])
}