알고리즘/Dynamic Programming15 [DP] 백준 1757번 - 달려달려 DP를 안 쓴다면) 매분 달릴지 말지를 결정하는 완전 탐색을 진행해야 한다. 2^N이 되는데 N DP? DP를 쓴다면) 상태 3가지 존재 1. 몇분 2. 지침 지수 3. 달리는 상태 dis[n] -> 각 시간에서의 갈 수 있는 거리 dp[x][y][z] -> '최대한 갈 수 있는 거리'로 dp를 설정 x : 분 y : 지침 지수 z : 달리는 상태 (1:달림 0:쉼) M은 2라고 가정 지침지수 0인 경우 y=0) dp[x][y][0] = max( dp[x-1][y+1][0], dp[x-1][y+1][1], dp[x-1][y][0] ) 지침지수 1인 경우 y=1) dp[x][y][0] = max( dp[x-1][y+1][0], dp[x-1][y+1][1] ) y-1에서 값을 가져올 수 없는 이유 >> y-.. 2021. 2. 5. [DP] 백준 15988번 - 1, 2, 3 더하기 3 생각하기 20을 나타내는 방법의 수 = 4를 나타내는 방법의 수 x 16을 나타내는 방법의 수 각 숫자 나타내는 방법의 수 구하는 방법 = 백트레킹? 하짐나 DP로 풀어야 하는 문제이기 때문에 DP적으로 생각! dp[num] = dp[num-1] + dp[num-2] + dp[num-3] 마지막에 각 단계에서 부족했던 숫자들만 더해서 값을 뽑을 수 있다 1을 구하는 방법에서 2을 더하는 방법 2를 구하는 방법에서 1을 더하는 방법 이미 구해 놓은 값들을 통해 구해낸다 * 각 숫자 때마다 dp값을 도출하기 #include #include #include #include #include #include #include #include #include using namespace std; #define end.. 2021. 1. 28. [DP] 백준 2748번 - 피보나치 수 2 case1) n이 0 혹은 1일 때, 0 / 1을 출력 case2) n이 2이상 일 때, memoizate해 놓은 이전 두개의 수를 더한 수를 출력 하지만 이런식으로 진행한다면 시간초과가 발생한다 memoization을 사용하여 연산을 최대한 줄여야 한다 #include #include #include #include #include #include #include #include #include using namespace std; #define endl '\n' int N; long long fib[100]; long long pibo(int n) { if(n==0){ return 0; } if(n==1){ return 1; } if(fib[n]!=-1) return fib[n]; else{ fib[.. 2021. 1. 25. 이전 1 2 3 4 다음