- 저 같은 경우 처음에 막혔던 부분이 보통의 dp문제에서 dp테이블은 각각의 n에 따른 정답? 을 가지고 있습니다.
- 이런식으로 짜려고 고민을 하다 보니 상당히 구현이 까다로웠습니다.
- 예를 들면 테스트케이스 가 1, 6, 2, 5, 7, 3, 5, 6 총 8개 인데
- 보통의 dp 테이블이면 만약 dp[6]을 뽑으면 최대치는 1,2,5,7 로서 4가 나와야 하고
- 이때의 상자의 바깥껍질의 크기인 7을 저장하면 dp[7]을 구하려고 할 때 1,2,5,7,과 1,2,3, +5 를 비교하는 것이 힘들었습니다.
- 설명하기가 조금 곤란한데, 비슷한 고민을 하신 분들은 공감을 하시리라....조심스럽게 생각해봅니다....
- 그래서 이 문제의 경우 n이하의 각각의 정답(즉 최대 상자의 수)를 dp에 저장하는 것이 아니라
- n에 크기를 늘려가면서 그때까지 차곡차곡 쌓기만한 크기를 저장해 놓은 다음 출력 전에 정렬을 해서 max 값을
- 출력하였습니다. 물론 정렬(소팅)을 하지않고 최대값만 갱신해도 상관 없습니다.
- 이런식으로 할경우 사실 정렬 전에 dp[6]에는 상자의 개수 3 (1,2,3) dp[5]에는 4 (1,2,5,7) 이 들어가 있습니다.
- 그러므로 n이 6일 때의 정답이 테이블에 들어가 있는 것은 아닌 것이죠. 정렬을 해서 출력을 해줘야 정답이 나오는
- 것 입니다. 하지만 이렇게 하면 문제의 요구사항에는 전혀 에러가 없고, 구현이 편해집니다.
2. 주의사항
- 위에 기재.
3. 나의코드
#include<bits/stdc++.h>
using namespace std;
int dp[1001]; // 사실상 정확한 dp를 가지고 있는 테이블은 아니다.
int n;
int narr[1001]; //상자의 크기
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) { //초기화
cin >> narr[i]; dp[i] = 1;
}
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (narr[i] > narr[j] && dp[i]<dp[j]+1) {
dp[i] = dp[j]+ 1;
}
}
}
sort(dp + 1, dp + (n + 1));
cout << dp[n];
return 0;
}
#include<bits/stdc++.h>
using namespace std;
long long n, m,tmp;
vector<long long> commitarr;
long long resulttime=1e18;
void inputs() {
cin >> n >> m; //n개의 심사대 , m 명의 친구들
for (int i = 0; i < n; i++) {
cin >> tmp; commitarr.push_back(tmp);
}
}
void findtime(long long l, long long h)
{
if (l > h) return;
long long mid = (l + h) / 2;
long long tmpsum = 0;
for (int i = 0; i < n; i++) {
tmpsum += (mid / commitarr[i]); //시간동안 각각의 심사대에서 심사가능인원
}
if (tmpsum >= m) {
if (resulttime > mid) { resulttime = mid; } //더 적은시간으로 가능하면 갱신
findtime(l, mid - 1);
}
else findtime(mid + 1, h);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
inputs();
sort(commitarr.begin(), commitarr.end());
long long lowtime = 1; long long hightime = commitarr[n - 1] * m;
//가장 오래걸리는 심사대에서 모두 받을 경우가 최대
findtime(lowtime, hightime);
cout << resulttime;
return 0;
}
- 이분 탐색을 통해 그것을 탐색해가면서 mid의 값이 아이들에게 조건에 맞게 나누어 줄 수 있는지 확인.
- 나누어 줄 수 있으면 더 작은 질투심을 유발할 수 있는 값이 있는지 mid보다 작은 쪽을 탐색.
- 아니라면 mid보다 큰 쪽을 탐색.
- 최소값을 출력하여 주었습니다.
2. 주의사항
- 없음.
3. 나의코드
#include<bits/stdc++.h>
using namespace std;
long long n, m;
long long numarr[300001];
long long result = 1e18;
bool canspread(long long mid) {
long long num = 0;
for (int i = 0; i < m; i++) {
num += numarr[i] / mid;
if (numarr[i] % mid) num++;
}
return n >= num;
}
int main() {
cin >> n >> m;
long long left = 1; long long right = 0;
for (int i = 0; i < m; i++) {
cin >> numarr[i];
if (right < numarr[i]) right = numarr[i];
}
while (left <= right) {
long long mid = (left + right) / 2;
if (canspread(mid)) {
if (result > mid) result = mid;
right = mid - 1;
}
else left = mid + 1;
}
cout << result << "\n";
return 0;
}
