99클럽 코테 스터디 29일차 TIL: DP

문제

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

풀이

전형적인 dp 문제이다.

초기값은 다음과 같다.
$f(1) = 1, f(2) = 1, f(3) = 1$

점화식은 다음과 같다.
$f(n) = f(n-2)+f(n-3)$

초기값과 점화식을 알면 DP 문제는 그냥 풀 수 있다.

소스코드

	let t = Int(readLine()!)!
	var dp = [Int](repeating: 0, count: 101)
	dp[1] = 1; dp[2] = 1; dp[3] = 1;
	for i in 4...100 {
	dp[i] = dp[i - 2] + dp[i - 3]
	}
	for _ in 0..<t {
	print(dp[Int(readLine()!)!])
	}

view raw 9461_파도반 수열.swift hosted with ❤ by GitHub

후기

어제 그저께 풀었던 dp 문제보다는 훨씬 쉬웠던 문제