[Swif_알고리즘] 백준 11726 타일링

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

 

 

 

접근 방법 (오답)

세로 막대 [] 가로 막대 = 라고 생각

길이가 n인 직사각형을 만들기 -> n1 * [] + n2 * 로 만들면 된다고 생각했다. 

이렇게 생각하면 '1'의 카드 n1개 와 '2'의 카드 n2개 를 배열하면 된다고 생각 했다.

따라서 while문과 factory문을 섞어서 구현하였다. 

func get14444() {
    let inputVal = Int(readLine()!)!

    var factoryArr:[Int] = Array(repeating: 0, count: inputVal + 1)
    func factorial (a :Int) -> Int {
        if factoryArr[a] == 0 {
            if a == 0 || a == 1 { return 1}
            let val = a * factorial(a: a - 1)
            factoryArr[a] = val
            return val
        }
        return factoryArr[a]
    }
    
    var a: Int = inputVal
    var b: Int = 0
    var count = 0
    while a > 0 && b < inputVal {
        count += factorial(a: a + b) / (factorial(a: a) * factorial(a: b))
        a -= 2
        b = b + 1
    }
    print(count)
}

get14444()

 

 

접근방법 (정답)

An의 관계식에 대해서 생각하면 편했다.

예를 들어서 A(n-1)에서 []만 더하고 A(n-2)에서는 =블럭만 더하면 되었다. 이렇게 생각하니

A(n) = A(n-1) + A(n-2)

 

func sol() {
    

    let inputVal = Int(readLine()!)!
    var targetArr = Array(repeating: 0, count: 1001)
    
    targetArr[1] = 1
    targetArr[2] = 2
    for i in stride(from: 3, to: inputVal + 1, by: 1) {
        targetArr[i] = (targetArr[i - 1] + targetArr[i - 2]) % 10007
    }
    print(targetArr[inputVal] % 10007)
    
}

sol()

 

 

다시짜니 깔끔하게 나와따.