첫 번째 나들이 OpenContest

https://www.acmicpc.net/contest/view/1215

첫 번째 나들이

 

내가 풀 수 있는 문제까지는 문제를 되게 잘 뽑았다 생각이 들었다.

 

A - 진주로 가자! (Easy)

간단한 A문제 jinju요금 저장하고 나머지와 비교하며 진주요금보가 큰 값을 count해주면 끝

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int n; cin >> n;
    vector<int> arr;
    int ans1, ans2 = 0;
    for (int i = 0; i < n; i++) {
        string s; int k; cin >> s >> k;
        if (s == "jinju")
            ans1 = k;
        else arr.push_back(k);
    }
    for (int k : arr) if (ans1 < k) ans2++;
    cout << ans1 << "\n" << ans2;
}

 

 

B - 진주로 가자! (Hard)

위 문제와 같은데 범위가 달라졌다.

교통편의 개수인 N이 5000000까지 늘어났고, 메모리 제한이 16MB로 줄었다.

즉, 크기 5000000인 배열을 만들면 메모리초과가 날 것이다.

이 문제를 해결하기 위해선 먼저 jinju교통편의 요금의 크기를 보면 최대 1000이다.

즉, 입력되는 값에서 1000이하의 값만 보면 되는 것이다.

그러면 1000크기의 배열이나 자료구조를 만들고, 저장만 해주면 된다.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int n; cin >> n;
    vector<int> arr(1001);
    int ans1, ans2 = 0;
    for (int i = 0; i < n; i++) {
        string s; long long k; cin >> s >> k;
        if (s == "jinju")
            ans1 = k;
        else {
            if (k > 1000) ans2++;
            else arr[k]++;
        }
    }
    for (int i = ans1 + 1; i <= 1000; i++) ans2 += arr[i];
    cout << ans1 << "\n" << ans2;
}

 

 

C - 선택의 기로

간단한 정렬문제.

문제에서 말하는데로 정렬기준을 해주면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#define pii pair<int, int>

using namespace std;

bool cmp1(pii o1, pii o2)
{
    if (o1.first == o2.first) return o1.second < o2.second;
    return o1.first > o2.first;
}
bool cmp2(pii o1, pii o2) {
    if (o1.first == o2.first) return o1.second > o2.second;
    return o1.first < o2.first;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int n; cin >> n;
    vector<pii> arr1(n);
    vector<pii> arr2(n);
    for (int i = 0; i < n; i++) {
        int q, p; cin >> q >> p;

        arr1[i] = { q, p };
        arr2[i] = { p, q };
    }

    sort(arr1.begin(), arr1.end(), cmp1);
    sort(arr2.begin(), arr2.end(), cmp2);

    cout << arr1[0].first << " " << arr1[0].second << " " << arr1[1].first << " " << arr1[1].second << "\n";
    cout << arr2[0].second << " " << arr2[0].first << " " << arr2[1].second << " " << arr2[1].first;

}

 

 

D - 육회비빔밥

문제를 보고 처음엔 머리에 "?"가 띄워졌다. 이게 순서가 상관없는건지, 상관이 있는건지 이해가 되지않았다.

그러다 최대 크기가 10인 것을 보고 "인덱스 순열을 모두 확인하면 되겠구나"생각이 들었다.

모든 순열을 확인하면서 문제에서 주어준 식을 통해 확인하면 끝이다.

#include <iostream>
#include <algorithm>
#include <vector>
#define pii pair<int, int>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int n, k; cin >> n >> k;
    vector<int> arrA(n + 1);
    vector<int> arrB(n + 1);
    vector<int> arrC(n + 1);
    vector<int> arrIdx;
    for (int i = 1; i <= n; i++) arrIdx.push_back(i);
    for (int i = 1; i <= n; i++) cin >> arrA[i];
    for (int i = 1; i <= n; i++) cin >> arrB[i];
    for (int i = 1; i <= n; i++) cin >> arrC[i];

    int ans = 0;
    do {
        int cur = 0;
        int curc = 0;
        for (int i = 1; i < n; i++) {
            cur += arrA[arrIdx[i - 1]] * arrB[arrIdx[i]];
            curc = arrC[arrIdx[i - 1]] * arrC[arrIdx[i]];
            if (curc > k) break;
        }
        if (curc <= k) ans = max(cur, ans);
    } while (next_permutation(arrIdx.begin(), arrIdx.end()));
    if (ans == 0) cout << -1;
    else cout << ans;
}

 

 

E - 닭강정의 전설

이 문제보고 바로 "구간 합 구하기5"문제가 떠올랐다.

2차원 배열의 누적합문제이다.

입력으로 주어진 구간의 테두리 부분의 누적합과 안의 누적합을 구하면 된다.

안의 누적합 * 2 - 입력으로 주어진 구간의 누적합을 해주면 정답이다.

안의 누적합을 *2를 하는 이유는 안의 누적합을 한번 빼주는 것으로 테두리의 누적합을 구하는 것이고, 그리고 안의 누적합 - 테두리의 누적합이 되기 때문이다.

#include <iostream>
#include <algorithm>
#include <vector>
#define pii pair<int, int>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n; cin >> n;
    vector<vector<int>> arr(n + 1, vector<int>(n + 1));
    
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> arr[i][j];

    for (int i = 1; i <= n; i++) for (int j = 2; j <= n; j++) arr[i][j] += arr[i][j - 1];

    for (int i = 1; i < n; i++) for (int j = 1; j <= n; j++) arr[i + 1][j] += arr[i][j];
    
    int q; cin >> q;
    
    for (int i = 0; i < q; i++) {
        int x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2;
        int other = 0;
        int sum = 0;
        sum = arr[x2 - 1][y2 - 1] - arr[x2 - 1][y1] - arr[x1][y2 - 1] + arr[x1][y1];
        other= arr[x2][y2] - arr[x2][y1 - 1] - arr[x1 - 1][y2] + arr[x1 - 1][y1 - 1];
        cout << sum * 2 - other << "\n";
    }
}

 

 

G - What's your ETA?

문제 자체는 간단하다.

버스 정류장의 재난 코드가 최대 값이 5000000이다.

그러면 소수를 확인해야하는 최대크기는 10000000이 되는 것이다.

이정도 크기면 에라토스네의 체를 써도 충분히 돌아간다.

소수판정을 하면 입력으로 간선이 주어질 때 이게 유효한 간선인지 체크해주고,

다익스트라로 최단거리를 구해주면 끝이다.

근데 아직도 이해가 안 가는 것, 처음 문제를 풀 때는 pq를 사용할 때 struct의 operator를 사용한 했는데 TLE가 났다.

진짜 이해가 안 갔다. 분명 시복 터질 코드가 아닌데 계속 TLE가 나서 미칠꺼같았다.

그러다 pair를 사용하는 대신 음의 값으로 넣어 정렬시키는 것으로 코드를 바꿨는데 AC를 받았다.

글쓰고 있는 지금도 아직 이해가 안 간다.

내일 다시 확인해보는 걸로...

#include <iostream>
#include <queue>
#include <cmath>
#include <climits>
#define pii pair<long long, long long>
#define ll long long
using namespace std;
ll INF = LLONG_MAX;
bool check[10000001];
int d[400001];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    for(int i = 2;i<=sqrt(10000000);i++){
        if(check[i]) continue;
        for(int j = i * i; j<=10000000;j+=i){
            check[j] = true;
        }
    }
    
    int n, m; cin >> n >> m;
    int maxs = 0;
    vector<vector<pii>> list(n + 1);
    for(int i = 1;i<=n;i++) cin >> d[i];
    for(int i = 0;i<m;i++){
        ll a, b, c; cin >> a >> b >> c;
        if(check[d[a] + d[b]]) continue;
        list[a].push_back({b, c});
        list[b].push_back({a, c});
    }
    vector<ll> w(n + 1, INF);
    priority_queue<pii> pq;
    w[1] = 0;
    pq.push({0, 1});
    
    while(!pq.empty()){
        pii now = pq.top();
        pq.pop();
        if(w[now.second] < -now.first) continue;
        for(pii next: list[now.second]){
            ll dist = -now.first + next.second;
            if(w[next.first] > dist){
                w[next.first] = dist;
                pq.push({-dist, next.first});
            }
        }
    }
    
    if(w[n] == INF) cout << "Now where are you?";
    else cout << w[n];
}

 

끝,,,,