CV에 혜택이! YTU 그리디 훈련 2(부분 주석)

경고: J 문제는 40분 동안 오류를 찾지 못해 시간 초과 발생(dp>검색) 간단한 문제 풀이(첫 번째 문제는 쉽게 해결됨) 1743 문제 A 

#include<bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 100010;
int n, k, sortedData[MAX_SIZE], accumulatedSum[MAX_SIZE], result, index1, index2, total;
int main() {
    cin >> n >> k;
    for(int i=0; i> sortedData[i];
    sort(sortedData, sortedData + n);
    while(index2 < n) {
        accumulatedSum[index1] += sortedData[index2];
        total += accumulatedSum[index1];
        index1++, index2++;
        if(index1 == k) index1 = 0;
    }
    printf("%.0lf", (double)total / n);
    return 0;
}
1757 문제 B 

#include<bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 100010;
struct Interval {
    int start, end;
    bool operator<(const Interval &other) const {
        return start < other.start;
    }
} intervals[MAX_SIZE];
int n, count;
int main() {
    cin >> n;
    for(int i=0; i> a >> b; if(a > b) swap(a, b);
        intervals[i] = {a, b};
    }
    sort(intervals, intervals + n);
    int currentEnd = intervals[0].end;
    for(int i=1; i
1002 문제 C 

#include<bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 100010;
int n, m, totalValue;
struct Item {
    double time, value, ratio;
    bool operator<(const Item &other) const {
        return ratio > other.ratio;
    }
} items[MAX_SIZE];
int main() {
    while(cin >> n >> m && n != 0) {
        memset(items, 0, sizeof(items));
        totalValue = 0;
        for(int i=1; i<=n; i++) {
            cin >> items[i].time >> items[i].value;
            items[i].ratio = items[i].value / items[i].time;
        }
        sort(items+1, items+n+1);
        for(int i=1; i<=n; i++) {
            if(m - items[i].time < 0) {
                totalValue += items[i].ratio * (double)m;
                break;
            }
            m -= items[i].time;
            totalValue += items[i].value;
        }
        printf("%.2lf\n", totalValue);
    }
    return 0;
}
2461 문제 D 

#include<bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 100010;
int n, count;
struct Point {
    int x, y;
    bool operator<(const Point &other) const {
        return y < other.y;
    }
} points[MAX_SIZE];
int main() {
    while(cin >> n && n != 0) {
        count = 0;
        for(int i=1; i<=n; i++) cin >> points[i].x >> points[i].y;
        sort(points+1, points+1+n);
        int currentEnd = points[1].y;
        for(int i=2; i<=n; i++) {
            if(points[i].x >= currentEnd) {
                count++;
                currentEnd = points[i].x;
            }
        }
        cout << count;
    }
    return 0;
}
1746 문제 E 

#include<bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 1000010;
int n, k, sortedArray[MAX_SIZE], result = 1;
int main() {
    cin >> n >> k;
    for(int i=0; i> sortedArray[i];
    sort(sortedArray, sortedArray + n);
    int currentEnd = sortedArray[0] + k;
    for(int i=1; i currentEnd) {
            result++;
            currentEnd = sortedArray[i] + k;
        }
    }
    cout << result;
    return 0;
}
2897 문제 F 

#include<bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 1000010;
int n, k, result;
struct Range {
    int start, end;
} ranges[MAX_SIZE];
bool compare(Range a, Range b) {
    if(a.end == b.end) return a.start < b.start;
    return a.end < b.end;
}
int main() {
    cin >> k;
    while(k--) {
        result = 1;
        cin >> n >> r;
        for(int i=1; i<=n; i++) {
            int a, b; cin >> a >> b;
            double x = sqrt(r*r - b*b);
            ranges[i].start = a - x;
            ranges[i].end = a + x;
        }
        sort(ranges+1, ranges+1+n, compare);
        int currentEnd = ranges[1].end;
        for(int i=2; i<=n; i++) {
            if(ranges[i].start > currentEnd) {
                result++;
                currentEnd = ranges[i].end;
            }
        }
        cout << result << endl;
    }
    return 0;
}
3394 문제 G 

#include<bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 100010;
int n, m, totalValue, sum;
struct Item {
    double value, cost;
    bool operator<(const Item &other) const {
        return value > other.value;
    }
} items[MAX_SIZE];
bool flag;
int main() {
    cin >> n >> m;
    int remaining = m;
    for(int i=0; i> a >> b >> c;
        sum += b;
        if(a > b) flag = true;
        totalValue += a * c;
        remaining -= a;
        items[i] = {b - a, c};
    }
    if(sum < m) flag = true;
    if(flag) {
        cout << "-1";
        return 0;
    }
    sort(items, items + n);
    for(int i=0; i
1310 문제 H 

#include<bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 100;
int n, values[5] = {1, 3, 9, 27, 81}, result[100];
string symbols;
bool found;
void dfs(int pos, int target, int current, int depth) {
    if(found) return;
    if(current == target) {
        for(int i=0; i target) {
        for(int i=pos-1; i>=0; i--) {
            result[depth+1] = values[i];
            symbols[depth] = '-';
            dfs(i, target, current - values[i], depth+1);
            result[depth+1] = 0;
        }
    } else {
        for(int i=pos-1; i>=0; i--) {
            result[depth+1] = values[i];
            symbols[depth] = '+';
            dfs(i, target, current + values[i], depth+1);
            result[depth+1] = 0;
        }
    }
    return;
}
int main() {
    cin >> n;
    int idx;
    if(n <= 81) {
        for(int i=0; i<5; i++) if(values[i] >= n) {idx = i; break;}
    } else idx = 4;
    result[0] = values[idx];
    dfs(idx, n, values[idx], 0);
    return 0;
}
3155 문제 I 

#include<bits/stdc++.h>
using namespace std;
int a, b, c, d, e, f, result;
int operations[4] = {0, 5, 3, 1};
int main() {
    while(cin >> a >> b >> c >> d >> e >> f && (a+b+c+d+e+f)!=0) {
        result = f + d + e + (c+3)/4;
        int temp = d*5 + operations[c%4];
        if(b > temp) result += (b - temp + 8)/9;
        int calc = 36*result - 36*f - 25*e - 16*d - 9*c - 4*b;
        if(a > calc) result += (a - calc + 35)/36;
        cout << result << endl;
    }
    return 0;
}
1914 문제 J (오랜 시간 소요, 조건을 놓쳤지만 해결함, 결과는 시간 초과) 

#include<iostream>
using namespace std;
int COUNT;
int coinValues[] = {1, 2, 5, 10, 20, 50, 100};
int dp[251][102][8] = {0};
int main() {
    for(int i=0; i<7; i++) dp[coinValues[i]][1][i] = 1;
    dp[1][101][0] = 1;
    for(int i=2; i<251; i++) {
        for(int j=1; j<=i && j<101; j++) {
            for(int k=6; k>=0; k--) {
                if(i > coinValues[k]) {
                    for(int l=k; l>=0; l--) {
                        dp[i][j][k] += dp[i - coinValues[k]][j-1][l];
                    }
                }
                dp[i][j][7] += dp[i][j][k];
            }
            dp[i][101][0] += dp[i][j][7];
        }
    }
    while(cin >> n && n != 0) {
        cout << dp[n][101][0] << endl;
    }
    return 0;
}
3509 문제 K 

#include<bits/stdc++.h>
using namespace std;
int data[1000010], n, result, sum[1000010];
int main() {
    cin >> n;
    for(int i=1; i<=n; i++) cin >> data[i];
    for(int i=1; i

태그: C++ Greedy Algorithm dynamic programming sorting data structures

7월 28일 23:16에 게시됨

인기 태그

©2026 괴물 클럽