#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
vector<int> arr;
int need(int width) {
// 색종이 폭이 width일때, 다 덮기 위해 필요한 종이의 수
int prev = -1;
int ret = 0;
for (int pos : arr) {
if (prev == -1) {
//처음 종이를 놓는 경우, [prev, prev+width) 까지 커버 가능
prev = pos;
ret++;
}
else if (prev + width <= pos) {
prev = pos;
ret++;
}
}
return ret;
}
int main() {
int row, col, num_paper, num_hole;
int max_height = 0;
cin >> row >> col >> num_paper >> num_hole;
for (int i = 0; i < num_hole; i++) {
int x, y; //행, 열
cin >> x >> y;
max_height = max(max_height, x);
arr.push_back(y);
}
sort(arr.begin(), arr.end());
int l = max_height;
int r = 1000000; //range = [l, r]
while (l < r) {
int m = (l + r) / 2;
if (need(m) <= num_paper) {
//가능한 경우
r = m;
}
else {
l = m + 1;
}
}
cout << l << endl;
return 0;
}
즉 1 500000 1000001 이렇게 인데, 사실 100만1은 안나오지만, 대충 타일 값 차이가 50만 가까이가
최대값이라고 보면 된다.
따라서 타일간 차이값인 diff값을 모두 다 찾아보면서 순회하려면 diff값이 50만개가 될 것이고
diff값 별 타일 모두를 다 훑어야 하므로 for-loop 도는 횟수는 50만 * 3천 정도 인데
이 값은 15억 정도 되므로, 15초 이상 걸리는 알고리즘 이라고 볼 수있다. 고로 Time Limit Exceed가
자명한 알고리즘이라는 뜻
그러면 이 계산량을 줄여야 하는데, N값이 3000이므로 꽤나 작다.
3000이라면 //(O(N^2)//)알고리즘을 짜도 돌아간다는 뜻.
여기서 잘 모르겠어서 아래의 알고리즘 분류를 "보기"를 눌러서 확인해 보았는데
다이나믹 프로그래밍이라고 힌트를 얻었다.
그러면 N값을 기준으로 메모이제이션 배열을 활용하면 될 것 같은데, N크기에 맞는 2차원 디피까지는 가능할 것 같다.
그렇다면 dp 배열 인덱스에 diff값을 넣을 수는 없다. 메모리 문제도 있고 시간 문제도 있고
그래서 //(dp[3000][3000]//)식으로 잡고, //(dp[i][j]//)라 했을 때, //(i//)가 마지막 인덱스고 //(j//)가 직전 인덱스로 해서
//(arr[i] - arr[j]//)로 diff값을 구할 수 있으니, 이를 활용해 보기로 했다.
dp[i][j] = i번째에서 끝나고, 그 직전에 arr[j]의 값을 갖는 시퀀스 합의 최대값
이라고 정의해보자.
처음 3개짜리만 대상으로 dp배열을 모두 전처리 해 놓은 뒤,
모든 dp배열을 돌면서, arr[j], arr[i]를 통해서 다음에 나올 수 있는 값을 구해서, 그 값이 존재하는 지
확인한 뒤, 존재한다면 그 인덱스를 //(k//)라 하고, //(dp[k][i]//)에 //(dp[i][j] + arr[k]//)를 넣는 식으로 구하면 될 듯하다.
값이 존재하는지는, 값의 범위가 1부터 100만이므로 배열을 잡기 보다는 c++ stl map같은 자료구조를 쓰면 좋을 것 같다.
배열로 잡는다면 값 자체는 3000개라서 sparse한 배열이 될 것이고, 메모리가 터질 수 있으므로
구현 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
int arr[3005];
map<int, int> mm;
ll dp[3005][3005]; // dp[i][j] => i번째에서 끝나고, 이전이 j인 시퀀스의 최대 누적합
int main() {
ll ans = 0;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int tmp;
cin >> tmp;
arr[i] = tmp;
mm[tmp] = i;
}
for (int i = 1; i < n; i++) {
int cur = arr[i];
for (int j = 0; j < i; j++) {
int prev = arr[j];
ll next = cur + (cur - prev);
if (mm.find(next) != mm.end()) {
int next_idx = mm[next];
dp[next_idx][i] = cur + prev + next;
ans = max(ans, dp[next_idx][i]);
}
}
}
for (int i = 1; i < n; i++) {
int cur = arr[i];
for (int j = 0; j < i; j++) {
if (dp[i][j]) {
int prev = arr[j];
ll next = cur + cur - prev;
if (mm.find(next) != mm.end()) {
int next_idx = mm[next];
dp[next_idx][i] = dp[i][j] + next;
ans = max(ans, dp[next_idx][i]);
}
}
}
}
cout << ans << endl;
return 0;
}
2008년도 초등부 문제 풀어보다가 1번 문제라서 쉽겠거니 하고 했다가 우수수 하고 틀려버렸다 ㅡㅡ
문제 내용은 크게 어려운 것은 없다.
규칙에 맞게 절사평균과 보정 평균을 구해주면 되는데, 배열로 받은 뒤 소팅해서
앞에 k개 만큼을 날리던지, 근처 값으로 변경해주던지 하면 된다.
하 그놈의 Floating Point 정확도 문제
Floating Point precision 문제때문에 하....
일단 입력값 중 점수는 0 ~ 10범위의 실수에 소숫점 한자리까지 나오는 floating point이고
전채 개수가 10만개 까지 나올 수 있다.
10만개라는 이유 때문에 precision 문제가 발생할 수 있다.
컴퓨터에서 사용하는 부동소수점 방식은 작은 에러값이 발생할 수 있다.
따라서 이게 누적되면 정확하지 않은 값이 나올 수 있는데
따라서 정수로 환원해서 풀어야 한다.
결과값은 소수점 2자리까지 출력해야하고, 이로 인해서 100을 곱하면 되겠지만, 소수점 셋째자리에서
반올림을 해야 하므로 1000을 곱해서 소수점 셋째자리까지 일단 표현 가능하게 정수로 받았다.
그리고 마지막에 5를 더해서 반올림을 구현했다.
출력할때는 1000을 나눈 정수 부분과 1000로 모듈러 연산을 한 소수부분(fraction)을 따로 출력해주었다.
5가 정답일 때 5.00라고 출력해야 하므로 포맷 스트링에 0 extension도 해 주어야 한다.
%02d와 같이 하면 너비 2만큼 0을 꽉채워서 출력해준다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
int main() {
int n, k;
vector<ll> arr;
cin >> n >> k;
arr.resize(n);
for (int i = 0; i < n; i++) {
double tmp;
cin >> tmp;
arr[i] = (ll)(tmp * 1000);
}
sort(arr.begin(), arr.end());
ll s = 0;
for (int i = k; i + k < arr.size(); i++) {
s += arr[i];
}
ll ans = s / (arr.size() - k - k) + 5;
printf("%lld.%02lld\n", ans / 1000, ans % 1000 / 10);
s = 0;
s += k * arr[k];
for (int i = k; i + k < arr.size(); i++) {
s += arr[i];
}
s += k * arr[arr.size() - 1 - k];
ans = s / arr.size() + 5;
printf("%lld.%02lld\n", ans / 1000, ans % 1000 / 10);
}
A번째 용액, B번째 용액을 골라서 확인을 하되, A번째 용액에 대해서는 for문 을 돌고, 각각 A번째용액에 대하여, B번째 용액을 결정할 때, 바이너리 서치 개념을 적용해서 풀어보았습니다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int a[100005];
int n;
int f, s, val;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", a + i);
}
f = a[0];
s = a[1];
val = abs(f+s);
for (int i = 0; i < n - 1; i++) {
int first = a[i];
int left = i + 1; // [left, right]
int right = n - 1;
while (left < right) {
int mid = (left + right) / 2;
int& second = a[mid];
int sum = first + second;
if (sum < 0) {
if (abs(sum) < val) {
val = abs(sum);
f = first;
s = second;
}
left = mid + 1;
}
else if (sum > 0) {
if (abs(sum) < val) {
val = abs(sum);
f = first;
s = second;
}
right = mid;
}
else {
cout << first << ' ' << a[mid] << endl;
return 0;
}
}
int second = a[right];
int sum = first + second;
if (abs(sum) < val) {
val = abs(sum);
f = first;
s = second;
}
second = a[left];
sum = first + second;
if (abs(sum) < val) {
val = abs(sum);
f = first;
s = second;
}
}
cout << f << ' ' << s << endl;
return 0;
}
이 풀이 외에도 O(N)으로도 풀이가 가능하다는 것을 알게 되었습니다.
배열이 정렬되어 있기 때문에, A번째에서 A+1번째로 이동할 때, 더 0에 가까운 값을 구하기 위해서는 B에서 B-1로 이동하는 경우는 있을 수 있으나 B+1에서 더 0에 가까운 값이 나올 수는 없기에 그리디하게 투포인터 형식으로 풀 수있습니다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int arr[100005];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", arr + i);
}
int a, b, val;
a = arr[0], b = arr[n - 1];
val = abs(a + b);
int left = 0;
int right = n - 1;
while (left < right) {
int l, r, sum;
l = arr[left];
r = arr[right];
sum = l + r;
if (abs(sum) < val) {
val = abs(sum);
a = l;
b = r;
}
if (sum > 0) {
right--;
}
else {
left++;
}
}
printf("%d %d\n", a, b);
}
색깔별로 다른 vector에 저장한 뒤, 정렬하여 인접한 녀석 중 가까운 곳에 잇는 방식으로 풀 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
vector<int> A[5005];
int main() {
int N;
cin >> N;
for (int i = 0; i < N; i++) {
int pos, col;
cin >> pos >> col;
A[col-1].push_back(pos);
}
for (int i = 0; i < N; i++) {
sort(A[i].begin(), A[i].end());
}
int ans = 0;
for (int j = 0; j < N; j++) {
for (int i = 0; i < A[j].size(); i++) {
int prev, next;
prev = next = 987654321;
if (i > 0) {
prev = A[j][i] - A[j][i - 1];
}
if (i + 1 < A[j].size()) {
next = A[j][i + 1] - A[j][i];
}
ans += min(prev, next);
}
}
cout << ans << endl;
return 0;
}
총N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다.N개의 방은 1번부터N번까지의 번호를 붙여 1번 방, 2번 방, …,N번 방으로 부른다. 통로는 정확히N-1개가 발견되었는데, 각각 서로 다른 두 방 사이를 연결시켜 주며 중간에 다른 통로와 이어지는 경우는 없다고 한다. 또한 이 통로들을 이용하여 임의의 두 방 사이를 이동하는 것이 가능하며, 임의의 두 방 사이를 이동할 때 같은 통로를 두 번 이상 지나지 않는 경로는 유일한 것으로 밝혀졌다.
이 조건을 보아서, 이 Graph는 트리입니다.
서로 다른곳에 있는 로봇이 만나기 위해 이동해야 하는 거리의 최소값을 구해야 합니다. 두 점의 최단거리 문제이죠.
그리고 한 Edge에 대해서는 이동하지 않고 통신을 할 수 있기 때문에, 그냥 최단거리 문제는 아닙니다.
Edge의 Weight값이 균일하지 않기 때문에 Dijkstra Shortest Path 알고리즘으로 풀 수 있으며, 한 Edge의 값은 제거할 수 있기 때문에 지난 Edge 중 가장 큰 Edge weight 값을 가지고 있다가, 총 거리에서 해당 Largest Edge weight를 제거하면 정답이 됩니다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
#define MAXN 100005
vector<pii> edges[MAXN];
bool visit[MAXN];
struct State {
int pos, totallen, maxseg;
bool operator<(const State& rhs) const {
return totallen > rhs.totallen;
}
};
int main() {
int N, A, B;
cin >> N >> A >> B;
for (int i = 1; i < N; i++) {
int src, dst, len;
cin >> src >> dst >> len;
edges[src].push_back(make_pair(dst, len));
edges[dst].push_back(make_pair(src, len));
}
priority_queue<State> pq;
pq.push({ A, 0, 0 });
while (pq.size()) {
State state = pq.top(); pq.pop();
int pos = state.pos;
visit[pos] = true;
if (pos == B) {
cout << (state.totallen - state.maxseg) << endl;
return 0;
}
for (auto next : edges[pos]) {
int next_pos = next.first;
int next_seglen = next.second;
if (visit[next_pos] == false) {
pq.push({ next.first, state.totallen + next_seglen, max(state.maxseg, next_seglen) });
}
}
}
}
아이디어를 생각해내기 좀 어려웠는데요, 풀고 나서도 왜 이게 풀렸는지 지금 100% 이해가 된 상태는 아닙니다.
일단 Graph 문제로 환원하여 생각을 하였고, 외부와 직/간접적으로 연결된 녀석들은 물이 셀 수 있습니다.
직접적으로 연결된 녀석은 그 연결된 구멍의 높이만큼 물이 세어나가게 되고, 간접적으로 연결된 녀석은 조건에 따라서 물이 세어나갈수도 있고 아닐 수도 있습니다.
외부에서 부터 Graph 탐색을 한다고 하였을 때, 간접적으로 외부와 연결된 내부 공간들이 탐색이 되게 되는데,
이때 외부로 연결되는 구멍의 높이가 높아지는 경우와 낮아지는 경우가 있습니다.
외부와 연결되는 구멍의 높이가 높아지는 경우는 최근 구멍의 높이만큼 물이 줄줄 세개 됩니다.
구멍의 높이가 낮아지는 경우는, 최근 연결된 녀석의 수심만큼만 물이 줄줄 세어나가게 됩니다.
이러한 특징을 활용해서 변형된 Dijkstra 최단거리 알고리즘으로 문제를 풀이했습니다.
구멍 높이가 낮은 녀석부터 먼저 탐색하도록 하였고, 이게 문제가 풀릴지 아닐지 몰랐는데, 풀리긴 하더군요.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
struct Edge{
int x, y, h;
};
struct State {
int x, y, sx, sy, h;
bool operator<(const struct State& rhs) const {
return h > rhs.h;
}
};
vector<Edge> edges[1005][1005];
int height[1005][1005];
bool visit[1005][1005];
int main() {
int N, M, H;
scanf("%d%d%d", &N, &M, &H);
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
height[i][j] = H;
}
}
for (int i = 0; i <= N; i++) {
for (int j = 1; j <= M; j++) {
/*
(i,j) ~ (i+1, j)
*/
int v;
scanf("%d", &v);
if (~v) {
edges[i][j].push_back({ i + 1, j, v });
edges[i + 1][j].push_back({ i, j, v });
}
}
}
for (int j = 1; j <= N; j++) {
for (int i = 0; i <= M; i++) {
/*
(j, i) ~ (j, i+1)
*/
int v;
scanf("%d", &v);
if (~v) {
edges[j][i].push_back({ j, i + 1, v });
edges[j][i + 1].push_back({ j, i, v });
}
}
}
priority_queue<State> pq;
for (int i = 0; i <= M + 1; i++) {
int x = 0;
int y = i;
visit[x][y] = true;
for (auto next : edges[x][y]) {
pq.push({ next.x, next.y, x, y, next.h });
}
}
for (int i = 0; i <= M + 1; i++) {
int x = N + 1;
int y = i;
visit[x][y] = true;
for (auto next : edges[x][y]) {
pq.push({ next.x, next.y, x, y, next.h });
}
}
for (int i = 1; i <= N; i++) {
int x = i;
int y = 0;
visit[x][y] = true;
for (auto next : edges[x][y]) {
pq.push({ next.x, next.y, x, y, next.h });
}
}
for (int i = 1; i <= N; i++) {
int x = i;
int y = M + 1;
visit[x][y] = true;
for (auto next : edges[x][y]) {
pq.push({ next.x, next.y, x, y, next.h });
}
}
while (pq.size()) {
auto state = pq.top(); pq.pop();
int x = state.x;
int y = state.y;
int sx = state.sx;
int sy = state.sy;
int h = state.h;
if (visit[x][y] == false) {
visit[x][y] = true;
height[x][y] = min(height[x][y], max(h, height[sx][sy]));
for (auto eg : edges[x][y]) {
if (visit[eg.x][eg.y] == false) {
pq.push({ eg.x, eg.y, x, y, eg.h });
}
}
}
}
int ans = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
ans += height[i][j];
}
}
printf("%d\n", ans);
return 0;
}
그리디로 풀 수 있다. 그리디도 그리딘데, 어떤식으로 그리디를 적용시킬지가 중요하다. 일단 배달 구간이 가장 짧은놈들 순서대로 sorting한다. 배달 구간이 짧을수록 트럭에서 공간을 점유하는 시간이 작아지므로 그렇게 하는 것이다.
그리고 배달구간이 짧은놈 순서대로 트럭에 최대한 집어넣으면 정답이 된다. 이것을 어떻게 구현하느냐에서 많이 해맸는데, 궂이 시간순대로 트럭이 이동하는 방식으로 시뮬레이션을 하지 않더라도 짧은 구간부터, 구간별 트럭에 적제된 화물양을 저장해놓았다가 최대한 적재시키는 식으로 정답을 구하면 쉽게 풀이가 된다.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii; //src, dst
struct Order {
int src, dst, size;
};
Order orders[10001];
bool cmp(const struct Order& lhs, const struct Order& rhs) {
if (lhs.dst != rhs.dst) return lhs.dst < rhs.dst;
return lhs.src < rhs.src;
}
int loaded[2001]; //해당 위치에 있을 때, 트럭에 차있는 양
int main() {
int ans = 0;
int n, c, m;
cin >> n >> c >> m;
for (int i=0; i < m; i++) {
scanf("%d %d %d", &orders[i].src, &orders[i].dst, &orders[i].size);
}
sort(orders, orders + m, cmp);
for (int i=0; i< m; i++) {
auto& order = orders[i];
int already_loaded_amount = 0;
for (int pos = order.src; pos < order.dst; pos++) { //구간을 돌면서 가장 많이 적제된 양을 찾는다.
if (loaded[pos] > already_loaded_amount) {
already_loaded_amount = loaded[pos];
}
}
int can_be_more_load_amt = min(order.size, c - already_loaded_amount); //더 적재할 양을 고른다.
for (int pos = order.src; pos < order.dst; pos++) { //구간에 적재 시킨다.
loaded[pos] += can_be_more_load_amt;
}
ans += can_be_more_load_amt;
}
cout << ans <<'\n';
return 0;
}
다이나믹 프로그래밍으로 문제를 해결할 수 있습니다. K값이 하나 뿐이므로, (시작점 -> K까지 경로)와 (K지점 -> 도착점까지 경로)를 나누어서 구해주면 된다. 숫자를 1부터 세므로 이에 따른 오류를 조심해야 한다.
get함수를 쓸 때 dp[x][y]는 시작 지점에서 (x, y)까지 도달 할 수 있는 경로의 개수를 뜻한다.
get2 함수를 쓸 때에는, (limitx, limity)에서 (x, y)로 도달할 수 있는 경로의 개수를 뜻한다.
get함수가 호출되었을 때에는 K지점을 기점으로 왼쪽과 위쪽부분의 부분 사각형에만 값이 들어가 있으며 또한 get2함수에서 (limitx, limity)보다 위쪽이나 왼쪽은 0으로 예외처리가 되어있게 처리되어있다.
#include <iostream>
using namespace std;
int dp[16][16];
int n, m, k;
int get(int x, int y) {
if (x < 0 || y < 0) return 0;
if (x == 0 && y == 0) return 1;
if (dp[x][y]) return dp[x][y];
return dp[x][y] = get(x-1, y) + get(x, y-1);
}
int get2(int x, int y, int limitx, int limity) {
if (x < limitx || y < limity) return 0;
if (dp[x][y]) return dp[x][y];
return dp[x][y] = get2(x-1, y, limitx, limity) + get2(x, y-1, limitx, limity);
}
int main() {
cin >> n >> m >> k;
if (!k) {
cout << get(n-1, m-1) << endl;
} else {
int xpos = (k-1) / m;
int ypos = (k-1) % m;
get(xpos, ypos);
cout << get2(n-1, m-1, xpos, ypos) << endl;
}
}
케이스를 잘 나누어야 한다. 일단 노선이 직선일 경우에 대하여 생각을 해 보자. 비교 연산자를 재정의해서 소팅해서, 시작위치는 오름차순으로, 끝 위치는 내림차순으로 정렬한다.
그러면 소팅을 하고 나서 선형탐색을 앞에서 뒤로 할 때, 뒤에 나타난 녀석이 앞에 있는 녀석을 포함하는 경우는 없다.
시작위치는 뒤로 갈 수록 앞으로 가기 때문에 시작 범위는 줄어들기 마련이다.
그리고 시작 위치가 고정인 상태에서는 끝나는 위치는 계속해서 작아지게 되어있으므로, 시작 위치가 다음 값이 되었을 때 끝 위치가 가장 큰놈 일 것이다. 이러한 점을 이용해서 끝놈 위치만 저장해 놓고, 끝놈보다 작으면 포함시켜버리고, 끝놈보다 크면, 그 끝놈 위치를 새 끝놈 위치로 저장해서 끝만 비교하면서 선형 탐색을 하면 된다.
그러면 또 노선이 원형일 경우를 체크를 해야 하는데, 시작점<끝점 의 경우 A그룹으로 정의하고 시작점>끝점 의 경우를 B그룹으로 정의를 하자. B그룹의 경우는 0번위치를 무조건 통과하고 A그룹은 0번 위치를 지나갈 수는 없다. 따라서 A그룹이 B그룹을 포함할 수는 없다.
B그룹에서 시작 부분의 최대값을 구하고, 끝 부분의 최소값을 구해서 A그룹의 (?~시작부분 최대값) 의 경우와 (끝부분 최소값~?)을 모두
포함할 수 있다. 이러한 경우를 체크해 주고(B가 A를 포함하는 경우) A그룹이 A를 포함하는 경우와 B그룹이 B를 포함하는 경우는 직선에서 비교하는 것과 똑같은 방법으로 체크하면 된다.
#include <bits/stdc++.h>
using namespace std;
int n, m;
struct Route {
int src, dst, num;
};
bool cmp(const struct Route& lhs, const struct Route& rhs) {
if (lhs.src != rhs.src) return lhs.src < rhs.src;
return lhs.dst > rhs.dst;
}
vector<Route> small, large; //인덱스 숫자가 작을수록 범위가 큰놈이다.
vector<bool> ans;
int main() {
cin >> n >> m;
ans.reserve(m+1);
int large_over = -1;
int large_below = n+1;
int over = 0;
for (int i=1; i<=m; i++) {
Route tmp;
scanf("%d %d", &tmp.src, &tmp.dst);
tmp.num = i;
if (tmp.src < tmp.dst) {
small.push_back(tmp);
} else {
large_over = max(large_over, tmp.dst);
large_below = min(large_below, tmp.src);
large.push_back(tmp);
}
}
sort(small.begin(), small.end(), cmp);
sort(large.begin(), large.end(), cmp);
//초기 large_over값은 large가 small 덮어쓰는 경우(0~over 범위로 덮는 경우임)
//초기 large_below값은 large가 small 덮어쓰는 경우(below~N) 범위로 덮는 경우
//진행하다보면 small이 small 덮어쓰는 경우도 있음
for (size_t i=0; i < small.size(); i++) {
if (small[i].dst <= large_over) ans[small[i].num] = true;
else if (small[i].src >= large_below) ans[small[i].num] = true;
if (small[i].dst <= over) {
ans[small[i].num] = true;
} else {
over = small[i].dst;
}
}
over = -1; //large가 large 덮어쓰는 경우
for (size_t i=0; i < large.size(); i++) {
if (large[i].dst <= over) ans[large[i].num] = true;
else over = large[i].dst;
}
for (int i=1; i <= m; i++) {
if (!ans[i]) {
cout << i << '\n';
}
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b, c, total;
cin >> a >> b >> c >> total;
int a_lim = total/a;
int b_lim = total/b;
int c_lim = total/c;
for (int i=0; i <= c_lim; i++) {
int cur = c * i;
for (int j=0; j <= b_lim; j++) {
int cur2 = cur + j*b;
for (int k=0; k <= a_lim; k++) {
int cur3 = cur2 + k*a;
if (cur3 == total) {
cout << 1 << '\n';
return 0;
}
}
}
}
cout << 0 << '\n';
return 0;
}
DFS를 통한 완전탐색으로 풀되, 중복되어 풀리는 문제들(Overlapping-subproblems)는 Memoization 패턴을 이용하여 중복해서 풀리지 않도록 처리했습니다. 그리고 마지막 구간까지 도달하지 못하는 경우에 대해서 제외하도록 처리해야하는 것이 좀 까다로웠습니다.
#include <bits/stdc++.h>
using namespace std;
#define IMPOSSIBLE -987654321
typedef long long ll;
int dp[101][100001]; //[range][minute left]
int walk_min[101];
int walk_get[101];
int bicy_min[101];
int bicy_get[101];
int n, k;
int get(int segment, int minute_left) {
if (segment >= n) return 0;
if (minute_left <= 0) return IMPOSSIBLE;
int& ret = dp[segment][minute_left];
if (ret != -1) {
return ret;
};
ret = IMPOSSIBLE;
if (minute_left >= walk_min[segment] and get(segment+1, minute_left - walk_min[segment]) != IMPOSSIBLE) {
ret = max(ret, get(segment+1, minute_left - walk_min[segment]) + walk_get[segment]);
}
if (minute_left >= bicy_min[segment] and get(segment+1, minute_left - bicy_min[segment]) != IMPOSSIBLE) {
ret = max(ret, get(segment+1, minute_left - bicy_min[segment]) + bicy_get[segment]);
}
return ret;
}
int main() {
scanf("%d %d", &n, &k);
for (int i=0; i < n; i++) {
scanf("%d %d %d %d", &walk_min[i], &walk_get[i], &bicy_min[i], &bicy_get[i]);
}
memset(dp, -1, sizeof(dp));
cout << get(0, k) << '\n';
return 0;
}
물론 나보다 앞에 있는 놈 중에 큰놈이 몇개인지 뿐만 아니라 누군지까지 확인할 수 있지만, 일단은 저 두개를 이용해서 문제를 풀어보았습니다.
맨 뒤에서 부터 채워가면서 숫자를 넣을 것인데, 일단 집합 S를 다음과 같이 초기화 합니다. S = {1, 2, 3, ... , N}
맨 뒤에있는 숫자 입장에서는 나머지 모두가 나보다 앞에 있으므로, 나머지 수 중 자신보다 큰 수가 몇개인지 알 수 있습니다.
그러면 앞에있는 수 중 자신보다 큰 수의 개수를 k라고 하면, 집합 S에서 k번째 큰 수를 빼서 자신의 값에 집어넣습니다.
이런식으로 맨 앞까지 진행합니다.
이러면 일단 조건을 만족할만한 정답 셋을 하나 구할 수 있는데, Valid한 정답을 갖는다면 Unique한 정답을 가질 것입니다.
하지만 해당 인풋이 Invalid할 수도 있으니 한번 체크를 해야 합니다. (Invalid한 정답이라면 -1를 출력해야함)
이때 Strict하게 체크를 하려면 자신보다 뒤에 있는 숫자 중, 순서쌍에 해당된다면 자신보다 작은지, 순서쌍에 해당되지 않는다면 자신보다 큰지를 확인해야하는데, 둘다 체크하게 되면 TLE가 날 것입니다.
특히나 순서쌍애 해당되지 않는 애들까지 체크를 하게 되면 O(N^2)이므로 꼼짝없이 TLE다. 하지만 순서쌍 개수는 100만개이므로, 순서쌍에 해당되는 경우만 체크할 경우 TLE는 안날 수 있습니다. 따라서 순서쌍에 해당되는 경우만 자신보다 작은 값을 갖는지만 체크하면 됩니다.
이 부분의 경우 -1이 정답인데 아니게 나올까봐 조마조마했는데 정답 판정이 났다. 아마 앞에서 만든 Answer Array가 주어진 순서쌍 조건이 맞는지만 확인해도빠진 조건이 있는 반례가 없다는게 논리적으로 맞아서 그런 것인지는 잘 모르겠습니다.
#include <bits/stdc++.h>
using namespace std;
#define NUM_STUDENT 100001 //학생수 최대
#define UNDEFINED 0 // 정답이 결정되지 않은 상태
set<int> larger_than_me[NUM_STUDENT], smaller_than_me[NUM_STUDENT];
int ans[NUM_STUDENT];
int n, m;
set<int> rest;
void fail() {
cout << -1 << '\n';
exit(EXIT_SUCCESS);
}
int main() {
scanf("%d%d", &n, &m);
//initialize rest set
for (int i=1; i<=n;i++) {
rest.insert(-i);
}
//initialize rest set
if (n == 1) { //학생수 1명일때만 예외처리
cout << 1 << '\n';
return 0;
}
for (int i=0; i < m; i++) {
int a, b;
scanf("%d %d", &a, &b); // a > b라는 뜻
smaller_than_me[a].insert(b); // a보다 작은 set에 b 추가.
larger_than_me[b].insert(a);// b보다 큰 set에 a추가.
}
for (int cur = n; cur >= 1; cur--) {
int larger_num = larger_than_me[cur].size();
auto it = rest.begin();
for (int i=0; i < larger_num; i++) {
it++;
}
int kth_largest = -*it;
ans[cur] = kth_largest;
rest.erase(it);
}
//check for validation - 주어진 조건은 맞는지 확인. 빠진 조건이 있는지는 안확인 ㅎㅎㅎ
for (int cur = 1; cur < n; cur++) {
int my_val = ans[cur];
for (auto it : smaller_than_me[cur]) {
int smaller_val = ans[it];
if (smaller_val > my_val) {
fail();
}
}
}
for (int i=1; i <= n; i++) {
cout << ans[i] << ' ';
}
cout << '\n';
return 0;
}
