25/01/09 백준일지

17275

발상적인 문제. 이걸 처음 본사람은 무슨 두뇌를 가졌을까
두종류의 간선을 가진 완전 연결 그래프에서 색이 섞이지 않은 삼각형 찾기 문제
단순히 하나하나 찾기에는 \(O(n^3)\)의 시간이 소요됨이 자명하다. 다만 간선이 두 종류밖에 없음을 떠올리고 전체 경우에서 간선의 종류가 다른 삼각형을 빼는 것을 떠올려보자. 그리고 각 점에서 (A색 간선) * (B색 간선)의 총합 / 2가 색이 다른 삼각형의 총개수다. 그를 통해 답을 얻어낼 수 있다.

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>

using namespace std;

ll adj[5050];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int tc; cin >> tc;
    while(tc--){
        ll n, m; cin >> n >> m;
        memset(adj, 0, sizeof(adj));
        while(m--){
            int a, b; cin >> a >> b;
            adj[a]++, adj[b]++;
        }
        ll ans = n * (n - 1) * (n - 2) / 6, del = 0; 
        for(int i = 1; i <= n; i++){
            del += (n - adj[i] - 1) * adj[i];
        }
        cout << ans - del / 2 << "\n";
    }
    return 0;
}

2388

언제나 문제는 내 구현능력
이러케이러케 하면 되겠다 라고 생각은 들지만 표현과 코드를 못짠다. 약간의 구현만 들어가도 절절매는걸 보면 구현문제를 좀 풀어야겠다. 문제는 초등학생때 했을 법한 방향별 블록의 개수를 보고, 최대최소를 구하는 문제다. 블록의 순서를 바꿔도 별 상관이 없고 처리를 용이하게 하기 위해 정렬을 해보자. 앞에서부터 천천히 값을 비교해보고 같을때는 다른칸으로, 다를 때는 적당히 경우를 나눠 보내주자자

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    vector<int> a(n), b(m);
    for(int &l : a) cin >> l;
    for(int &l : b) cin >> l;
    if(n < m){
        swap(n, m); swap(a, b);
    }
    sort(a.begin(), a.end(), greater<>());
    sort(b.begin(), b.end(), greater<>());
    a.push_back(0); b.push_back(0);
    if(a[0] != b[0]){
        cout << -1;
        return 0;
    }
    int scnt = 0, lcnt = 0;
    for(int fnt = 0, sid = 0; fnt < n || sid < m;){
        if(a[fnt] == b[sid]){
            scnt += a[fnt];
            lcnt += ((fnt + 1) * (sid + 1) - fnt * sid) * a[fnt];
            fnt++; sid++;
        }else if(a[fnt] > b[sid]){
            lcnt += sid * a[fnt];
            scnt += a[fnt];
            fnt++;
        }else{
            lcnt += fnt * b[sid];
            scnt += b[sid];
            sid++;
        }
        if(fnt > n) fnt = n;
        if(sid > m) sid = m;
    }
    cout << scnt << " " << lcnt;
    return 0;
}