[BOJ] 백준 1904 01타일 (Swift)

문제

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

1904번: 01타일

풀이

다이나믹 프로그래밍으로 풀 수 있는 문제입니다.

N이 1일 때는 1만 만들 수 있고, N이 2일 때는 00, 11 로 두 가지를 만들 수 있습니다.

N이 3일 때는 어떠할까요?
N이 1일 때의 경우에서 "00" 타일 붙히기 + N이 2일때에서 "1"타일을 붙히기 일 것입니다.
따라서 100, 001, 111 로 3가지 경우일 것입니다.

이렇게 이전의 결과들을 바탕으로 다음 결과를 도출할 수 있습니다.

점화식 : $f(n) = f(n - 1) + f(n - 2)$
초기값 : $f(1) = 1, f(2) = 2$

소스코드

	let n = Int(readLine()!)!
	var cache = [Int](repeating: 0, count: 1_000_001)
	cache[1] = 1
	cache[2] = 2
	for i in 3...1_000_000 {
	cache[i] = cache[i - 1] + cache[i - 2]
	cache[i] %= 15746
	}
	print(cache[n])

view raw 01타일.swift hosted with ❤ by GitHub

후기

다이나믹 프로그래밍 문제중에 그나마 풀만했던 문제였습니다.
다이나믹 프로그래밍 너무 어렵다..😂