목록다이나믹 프로그래밍 (63)

1일1알

백준 7579번 앱 C++

다이나믹 프로그래밍으로 풀 수 있는 문제이다. 배낭 문제와 비슷하다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n, m; int sum = 0; vector v; vector cache(101, vector(10001, 0)); int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; v = ve..
알고리즘 2022. 7. 8. 12:27
백준 10942번 팰린드롬? C++

메모이제이션 기법을 이용해서 풀었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n, m; vector v; vector cache; int DP(int start, int end) { int& ret = cache[start][end]; if (start >= end) return ret = 1; if (cache[start][end] != -1) return ret; if (v[start] != v[e..
알고리즘 2022. 7. 7. 10:59
백준 2193번 이친수 C++

맨 뒷자리가 0으로 끝날때와 1로 끝날때를 나눠서 생각했다. 0으로 끝날때는 다음에 1이나 0 아무거나 와도 되고, 1로 끝날때는 0만 와야한다. dp[i][0]=dp[i-1][0]+dp[i-1][1] dp[i][1]=dp[i-1][0] 이 점화식을 이용해서 문제를 풀었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL..
알고리즘 2022. 5. 26. 12:48
백준 2096번 내려가기 C++

최대 점수 : dp[i][j] = 붙어있는 dp[i-1]중 MAX + v[i][j] 최대 점수 : dp[i][j] = 붙어있는 dp[i-1]중 MIN+ v[i][j] 인데, 메모리 제한이 4MB 이기 때문에 2차원 배열을 만들지 않고 입력받는대로 값을 갱신하면서 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(..
알고리즘 2022. 3. 31. 11:24
백준 2688번 줄어들지 않아 C++

다이나믹 프로그래밍으로 문제를 해결하였다. dp[i][j] 의 2차원 dp배열을 만들고 이 배열의 의미는 i자리 수의 마지막 숫자가 j일 때 줄어들지 않는 수의 개수이다. i자리 수의 마지막 숫자가 j일 때 줄어들지 않는 수의 개수는 i-1자리 수의 마지막 숫자가 0~j일 때 줄어들지 않는 수들의 합이다. 즉, dp[i][j] = dp[i-1][0] + .... + dp[i-1][j] 이다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using ul..
알고리즘 2022. 3. 19. 10:43
백준 9084번 동전 C++

dp로 해결할 수 있는 문제이다. 배낭 채우기 문제와 비슷하다. dp[n+1][m+1]배열을 만들었다. dp[i][j]의 의미는 i번 동전까지 사용해서 j원을 만들 수 있는 경우의 수 라고 정하였다. 동전 몇개로든 0원은 언제나 만들 수 있어서 dp[i][0]은 모두 1로 초기화 해주었다. i번째 동전까지 사용해서 j원을 만들 수 있는 경우는 1) i-1번째 동전까지 사용하고 j원을 만든 상태에서 아무 행동도 하지 않는 경우와 2) i번째 동전까지 사용했는데 j-coins[i]원을 만든 상태에서 coins[i]를 추가해서 j원을 만드는 경우가 있다. 따라서 점화식은 dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]] 로 세우고 문제를 해결하였다. #include #include #..
알고리즘 2022. 3. 15. 11:52
이전 Prev 1 2 3 4 5 6 7 ··· 11 Next 다음