백준 2748, 1003, 1904.
--
(스포를 조금 하자면 셋다 Fibonacci 관련 문제임).
1) 2748 (https://www.acmicpc.net/problem/2748)
Just Fibonacci문제.
Recursion 방식으로 하면 Time Complexity에 문제가 있으니 DP방식으로 풀면 좋음.https://github.com/JangJuMan/2019-winter-PS/blob/master/DP/1_2748.cpp
2) 1003 (https://www.acmicpc.net/problem/1003)
Fibonacci에서 0과 1이 몇번씩 call 되는지를 묻는 문제.
역시 Recursion 방식으로 하면 Time Complexity에 문제가 있으니 DP방식으로 품.
(DP파트인데 이걸 쓰는 의미가 있나..? ㅎ)암튼, 0과 1이 불리는 횟수에 대한 DP 배열를 만들어 놓고
F(N) = F(N-1) + F(N-2) 점화식을 통해 배열 완성하기.예를들면,
(* 0 array : 0이 불리는 횟수, 1 array : 1이 불리는 횟수, fibo array : 피보나치 값 array)
[index : ]
0 1 2 3 4 5 6 7 8 9 10
[0 array : ]
1 0 1 1 2 3 5 8 13 21 34
[1 array : ]
0 1 1 2 3 5 8 13 21 34 55
[fibo array : ]
0 1 1 2 3 5 8 13 21 34 55https://github.com/JangJuMan/2019-winter-PS/blob/master/DP/1_1003.cpp
3) 1904 (https://www.acmicpc.net/problem/1904)
00이라는 타일이 붙어있는 상황에서 N자리 수의 이진수를 몇개까지 만들 수 있는지를 묻는 문제.
손으로 쓰다보면 규칙을 발견할 수 있음.
만들 수 있는 이진수의 개수가 1 > 2 > 3 > 5 > 8 ... 이런 식으로 증가함.왜 그렇게 나오나?
0 이라는 타일이 00으로 붙어버린 것은
자리수가 하나 늘었다고 해서 00 타일을 붙일 수가 없다는 것을 의미함.따라서 00타일을 붙일 수 있는 경우는 두 자리수가 늘었을 경우임.
반대로 1 타일은 자리수가 하나 늘었을 때 붙일 수 있음.
(근데 자리수 2개 늘었다고 1 타일을 붙이면 이전에 1타일 붙인 것이랑 중복되니까 이때는 세면 안됨)결론적으로 n번째 자리수의 이진수는
n-1번째의 수 중에서 뒤에 1을 붙인 경우와
n-2번째의 수 중에서 뒤에 00을 붙인 경우이다.
(앞뒤로 붙이는 경우도 생각했었는데 그러면 결국 중복되서 의미가 없어짐).암튼 그래서 점화식을 정리해보면 F(n) = F(n-1) + F(n-2)라는...!
다만 보통 피보나치 수열과는 다르게 F(1) = 1, F(2) = 2이니까 주의하기.
https://github.com/JangJuMan/2019-winter-PS/blob/master/DP/1_1904.cpp
끝
