알고리즘90 머지소트 #include using namespace std; const int MAX = 1e5; int n, a[MAX], b[MAX]; void msort(int st, int en) { if (st == en) return; int mid = (st + en) / 2; msort(st, mid); msort(mid + 1, en); int i = st, j = mid + 1, k = 0; while (i a[i]; msort(0, n - 1); for (int i = 0; i < n; i++) cout 2020. 1. 2. codeforces #610 div2 B2 - K for the Price of One (구현) https://codeforces.com/contest/1282/problem/B2 빡구현 초기 돈 p와 세트로 살 수 있는 묶음단위 k, 최대 2e5개의 물품 가격이 주어질 때, 최대한 많은 물품을 구하는 경우 몇개를 사는지 구하는 문제. 한번 물건을 살 땐 단 한개를 사거나 딱 k개를 사야 한다. k개 묶음을 살 땐 가장 비싼 물품에 대해만 돈을 내면 된다. 돈 6, 묶음단위 3, 가격 2 3 4 5 7 8이 주어질 때를 생각해보면.. (초기돈은 신경쓰지 말자) 물건 1개 살 때 -> (2) 가격:2 물건 2개 살 때 -> (2),(3) 가격:5 -> 일단 신경쓰지 않는다. 더 싼 값으로 더 많이 살 수 있기 때문. 물건 3개 살 때 -> (2,3,4) 가격:4 물건 4개 살 때 -> (2),(3,4.. 2019. 12. 30. BOJ 2228 - 구간나누기 (dp) https://www.acmicpc.net/problem/2228 최대 100자의 숫자배열을 입력 받았을 때 연속된 수열을 총 m개 뽑을 때 그 뽑힌 숫자들의 최대값을 구하는 문제. **dp값을 처음 초기화 할 때 특정 값으로 초기화 하기가 애매하다. 숫자가 음수일 수 있기 때문. 따라서 bool타입 c[101][51]을 사용해서 지금 상태가 이미 메모된 상태인지 기록해둔다. (psum 사용하므로 1-base ) f(i, j) : 1 ~ i 번째 숫자를 사용하여 j개의 연속된 수열을 뽑을 때 뽑힌 숫자들의 최댓값 f(i, j) = max(i번째 숫자를 뽑지 않을 때, i번째 숫자를 뽑을 때) 1. i번째 숫자를 뽑지 않는 경우 f(i,j) = f(i-1, j) 2. k번째 ~ i번째 숫자를 뽑는 경우 f.. 2019. 12. 29. BOJ 11049 - 행렬 곱셈 순서 (dp) https://www.acmicpc.net/problem/11049 파일 합치기와 매우 유사함 최대 500개의 행렬 정보가 n*m 형태로 입력될 때, 이들은 순서대로 곱할 수 있음이 보장된다. 모든 행렬을 곱할 때 곱셈 연산의 최소횟수를 구하는 문제. f(i, j) : i~j번째 행렬을 곱할 때 곱셈 연산의 최소 횟수 f(i, j) = f(i,k) + f(k+1,j) + a[i].f * a[k+1].f * a[j].s ( i > a[i].first >> a[i].second; memset(dp, -1, sizeof(dp)); cout 2019. 12. 29. 이전 1 ··· 5 6 7 8 9 10 11 ··· 23 다음