프로그래머의 개발노트

https://www.acmicpc.net/problem/1003 - 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다. - 출력 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. - 풀이 문제에 피보나치 함수에 대한 코드가 주어져 있는데, f(n) = f(n - 1) + f(n - 2) 위의 식을 잘 생각해보면 Base Case인 if(n == 0) return (0);else if (n == 1) return (1); 이 부분을 만날 때 까지 저 식을 타고 타고 들어간다고 생각해 보면 됩니다. n = 3 일 경우를 예시로 들어보면, f(3) = f(..

https://www.acmicpc.net/problem/9095 - 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. - 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. - 풀이 1,2,3 까지 구할수 있는 경우를 생각해보자. - 1 1 - 2 1+12 - 31+1+11+22+1 이제 4를 생각해보면, 3에서 구했던 값들에 1을 더하고, 2에서 구했던 값들에 2를 더하고, 1에서 구했던 값들에 3을 더하면 된다. 1+1+1+11+2+12+1+1=> dp(3)의 갯수와 동일 1+1+22+2=> dp(2)의 갯수와 동일 1+3=> dp(1)의 갯수와 동일 따라서, 점화식은 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] (n >= 4)로 세울 수 있겠..