[BOJ] 백준 9095 1, 2, 3 더하기 (Swift)
문제https://www.acmicpc.net/problem/9095풀이dp로 쉽게 풀 수 있는 문제이다.1을 만드는 방법은 1 단 하나이다.2를 만드는 방법은 1 + 1, 2 두개3을 만드는 방법은 1 + 1 + 1, 2 + 1, 1 + 2, 3 총 4개이다.여기서 4를 만드는 방법을 구하면 다음과 같이 해석할 수 있다.1을 만드는 방법 + 32를 만드는 방법 + 23을 만드는 방법 + 11, 2, 3을 이용해 4를 만드는 방법은 총 7가지다.5, 6, 7.. 도 동일하게 적용할 수 있다.점화식은 다음과 같다.$f(1) = 1, f(2) = 2, f(3) = 4$$f(n) = f(n-3) + f(n-2) + f(n-1)$소스코드후기기본적인 dp 문제였다.
[BOJ] 백준 1003 피보나치 함수 (Swift)
문제https://www.acmicpc.net/problem/1003풀이시간제한이 0.25초로 짧은 편에 속하는 문제이다.문제에서 주어진 대로 소스코드를 짠다면 시간복잡도는 $O(2^n)$이고, n이 최대 40이므로 0.25초 내에는 풀 수 없어 다른 방법으로 풀이해야한다.f(2)를 구한다면 f(1), f(0)이 호출된다.f(3)은 f(2) + f(1) 이므로, f(3) = f(1) + f(0) + f(1)이된다.f(4)는 f(3) + f(2) 이므로 ...f(0) = (0, 1), f(1) = (1, 0) 로 초기값을 설정하여, dp를 활용해서 풀 수 있을 것 같아서 풀이하였다.$f(n) = f(n - 1) + f(n - 2)$$f(0) = (0, 1), f(1) = (1, 0)$이는 $O(n)$의 시..
