김미썸코딩

이문제는 가장 긴 증가하는 부분수열(LIS)을 푸는 방식과 매우 비슷하다. 다만 여기선 가장 긴 감소하는 부분 수열을 찾는 문제이며 최댓값을 찾아내는 것이고 순서는 상관없기 때문에 입력받은 값을 reverse시켜서 가장 긴 증가하는 부분 수열처럼 처리하면 된다. #include #include #include #include using namespace std; int n; vector v; int main(void) { cin >> n; for (int i = 0; i > x; v.push_back(x); } // 순서를 뒤집어 '최장 증가 부분 수열' 문제로 변환 reverse(v.begin(), v.end()); // 다이나믹 프로그래밍을 위한 1차원 DP..

▶ 내 풀이 #include #include #include #include #include using namespace std; int t, n, m; const int MAX = 21; int dp[MAX][MAX]; int main(void) { cin >> t; for (int i = 0; i > n >> m; for (int j = 0; j > x; dp[j][k] = x; } } // 두번째 열부터 for (int y = 1; y < m; y++) { for (int x = 0; x < n; x++) { int max_num = ..

한 재작년이나 작년쯤 뭣도 모르고 코테를 쳤을 때.. 이런비슷한 문제들을 많이 봤다. 다이나믹 프로그래밍을 몰랐기 때문에 가장 큰 화폐단위부터 나누어 떨어지느냐 아니냐로 매달리다가 포기했던 기억이있다... 위의 문제 해결 아이디어를 보면 점화식으로 문제를 해결하는것과 같다. 아래와 같이 인덱스 값이 나오기 위한 결과값을 담을 배열을 만든다. 그 배열은 M의 최댓값이 10000이므로 크기가 M+1이고 초깃값이 전부 10001인 배열이다. 0은 어떠한 화폐단위로도 만들 수 없으므로 인덱스가 0인 자리엔 0을 넣는다. 다음 화폐 단위가 작은 것부터 반복문을 돌린다. 반복문이 시작은 화폐단위이고 끝은 M이 된다. 예를 들어, 아래처럼 화폐단위가 2이고 M이 7일 때 2부터 7까지가 된다. 아래는 화폐단위 2에 ..

다이나믹 프로그래밍으로 해결할수 있는 문제이다. 개미전사가 주어진 식량창고에서 얻을 수 있는 식량 최댓값을 구하는 문제인데 그리디나 구현으로 푸는 것보다 작은 요소의 해결책을 쌓아서 큰문제의 해결책을 찾는 다이나믹 프로그래밍이 훨씬 효율적인 문제다. 바텀업 방식으로 해결했다. #include #include #include #include #include using namespace std; int d[100]; int N; vector arr; int main() { cin >> N; for (int i = 0; i > x; arr.push_back(x); } d[0] = arr[0]; d[1] = max(arr[0], arr[1]); for (int i = ..