[Swift Algorithm] 2×n 타일링 BOJ #11726

문제 설명

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

 

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

 

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

입출력 예제

입력

9

출력

55

 

내 문제 풀이

let N = Int(readLine()!)!
var dp = Array(repeating: 0, count: 1001)

func solution(_ n: Int) -> Int {
    if n == 1 { return 1 }
    if n == 2 { return 2 }
    if dp[n] > 0 { return dp[n] } // 중복을 피하기 위함
    dp[n] = (solution(n-2) + solution(n-1)) % 10007
    return dp[n]
}

print(solution(N))

👉 DP 문제로, 점화식을 구해주는게 포인트!

 

[점화식]

• n이 1일 경우 답은 1
• n이 2일 경우 답은 2
• n이 3일 경우 답은 3
• n이 4일 경우 답은 5
• n이 5일 경우 답은 8

=> 이전 두 수의 답을 구한 값이 현재의 답이 되는 것을 확인할 수 있다.

=> dp[n] = dp[n-1] + dp[n-2] 

 

[코드 설명]

• n이 1, 2일 경우에는 이전 두 수가 존재하지 않으므로 바로 해당하는 답을 return했다.
• dp[n]이 0보다 클 경우(0이 아닐 경우) dp[n] 값을 그대로 return했다.
  => dp[n]에 0이 아닌 어떤 값이 저장되어있다는 것은 이미 dp[n]은 계산된적이 있다는 의미이다.
  굳이 중복된 계산을 또 해줄 필요는 없기 때문에 연산 없이 그대로의 값을 리턴한다.
  (dp알고리즘의 핵심과도 같은 부분이기도 함. 👇이전 게시글 참고!)
  2021.08.28 - [📍 Algorithm Note/🔍 with Swift] - [Swift Algorithm Note] 동적 계획법 (feat. Fibonacci)
•  위의 예외에 걸리지 않은 경우에는 재귀 호출로 점화식을 구현해주었다.

 

💡 피드백

• 처음엔 중복을 피해주는 코드를 작성하지 않아서 계속 시간초과가 났었는데,
  디버깅하면서 확인해보니까 계속 중복된 계산을 하고 있다는 것을 알 수 있었다.
  DP인만큼, 중복에 대해서 더 신경써주어야 할 것 같다.

 

---

문제

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