동적계획법3 cpp) 백준 1463: 1로 만들기 Problem https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net Solution #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int n; cin >> n; int dp[10000001]; dp[0]=0; dp[1]=0; dp[2]=1; dp[3]=1; for(int i=4;i 2023. 7. 15. cpp) 백준 1003: 피보나치 함수 Problem https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net fibonacci(3)의 경우 1은 2번 출력되고, 0은 1번 출력된다. fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오. Solution 매번 재귀함수를 호출해서 수를 구한다면 시간 초과가 뜨기 때문에 규칙성을 찾아 문제를 해결해야 한다. 과정을 짚어보면, '0 호출 횟수'와 '1 호출 횟수' 모두 기존의 피보나치 함수와 유사한 것을 확인할 수 있다. n 피보나치 수 0 호출 횟수 1 호출 횟수 0 0 1 0 1 1 0 1 .. 2023. 6. 10. cpp) 백준 11050: 이항 계수 1 Problem https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 자연수 N과 정수 K가 주어졌을 때 이항계수를 구하시오. Solution #include #include #include using namespace std; int cache[11][11]; int bino2(int n, int k){ // 기저 사례 if (k==0 || n==k) return 1; // cache[n][k] 값이 존재할 경우 if (cache[n][k]!=-1){ return cache[n][k]; } return cache[n][k] .. 2023. 6. 8. 이전 1 다음
