Dynamic Programming17 [C] 11659: 구간 합 구하기 4 그냥 bruteforce하게 이중 for문을 이용해서 푼다면 시간초과가 나온다. 이때 구간 합을 이용하여야 하는데 i번째까지 합을 dp[i]에 저장하였다가 합을 구해야하는 구간에 대해서 result=dp[b]-dp[a-1]; 를 통해 구하면 된다. DP라고 보기에는 애매할 수도 있으나 중복되는 부분 문제를 줄일 수 있다는 점에서 의의가 있는 것 같다. 이건 꼭 알아야한다! 구간 합을 이용하면 시간복잡도를 n^2에서 n으로 획기적으로 줄일 수 있다! #include int arr[100001]; int dp[100001]; int main(void) { int n,m; scanf("%d %d",&n,&m); for(int i=1;i 2023. 8. 21. [C] 1003: 피보나치 함수 피보나치!!하면 바로 Dynamic Programming으로 풀어야겠다는 생각이 들어야한다! 가장 대표적이면서 기본적인 DP 문제가 피보나치랑 이항계수 관련된 문제이기 때문이다 예시와 같이 피보나치 함수를 f(n)부터 구한다면 호출의 개수가 n이 조금만 증가해도 기하급수적으로 늘어난다. 그렇기 때문에 f(0)과 f(1) 부터 배열에 저장하면서 f(n)을 구해야만 효율적으로 호출할 수 있다. 이 문제에서도 n이 1,2,3...증가할 수록 호출하는 f(0)과 f(1)의 개수가 피보나치 수열의 점화식을 따른다. 그렇기 때문에 이것을 배열에 미리 저장한 후 테스트케이스가 주어지면 불러오면 되는것이다 #include int arr[500001]; int fibo_0[41]; int fibo_1[41]; int m.. 2023. 8. 3. [C] 2748: 피보나치 수 2 그냥 피보나치 수열을 만들면 된다. 다만 범위가 int형을 벗어나기 때문에 long long int를 사용해야한다는 것만 주의하면 쉽게 풀 수 있다!! #include int long long fibo[91]; int main(void) { int n; scanf("%d",&n); fibo[0]=0; fibo[1]=1; fibo[2]=1; for(int i=3;i 2023. 7. 30. [C] 1149: RGB거리 전형적인 Dynamic Programming 문제인걸 알 수 있었는데 그 이유는 subproblem을 여러번 이용해야하기 때문에 이를 위해서 dp[]에 저장해서 이용해야했고 최솟값과 관련된 문제였기 때문이다. 이 문제는 i=1일때부터 하나하나씩 해보면 점화식을 구하는 것보다는 i=n일때부터 거꾸로 생각하는게 좀 더 떠올리는게 쉬웠던 것 같다. (2Xn 타일링2와 같이!) 그리고 빨강,초록,파랑 각각을 선택했을때 최선인 경우를 따로따로 저장하는 것이 각각 생각하지 않고 dp[i]일때 최선인 것을 저장하는 것보다 효율적이었는데 이는 똑같은 색깔을 두번 연속 선택하지 못한다면 그 다음에 최선인 경우를 빨리 찾기 위해서이다. #include int red[1001]; int green[1001]; int blu.. 2023. 7. 30. 이전 1 2 3 4 5 다음