10.31~11.3

 중간고사는 2승 1무 1패 정도 한 듯 하다.  실험 보고서 두 개를 다음주가 오기 전에 적어야 하는데 밀린 공부 먼저 하고 가는게 정신건강에 좋겠다.  코딩을 안한게 딱 중간고사 준비 기간만큼이라 상대적으로 쉬운 문제를 먼저 푼다.

1. A+B - 6: https://www.acmicpc.net/problem/10953

for _ in range(int(input())):print(sum(map(int, input().split(","))))

python3, 한 줄 코딩

 

2. 셀프 넘버: https://www.acmicpc.net/problem/4673 

#include <iostream>

using namespace std;
int arr[10001]; // all zero
int main(){
    for(int k = 1; k <= 10000; k++){
        if(!arr[k]){
            for(int j = k; j <= 10000;){
                int v = j;
                while(v>0){
                    j += (v % 10);
                    v /= 10;
                }
                arr[j] = 1;
            }
        }
    }
    for(int i = 1 ; i <= 10000; i++){
        if(!arr[i]) cout << i << endl;
    }
    return 0;
}

 10000개의 배열에서 가능한 수를 찾는 문제다.  에라토스테네스의 체에서 소수를 곱한 것들을 다 빼는 것과 똑같다.  시간 제한이 1초이므로 O(n^2)이라 1억번을 돌기에 시간안에 들어올 수 있다.  또한 안의 루프를 도는데서 최악의 경우를 만족하는 경우는 없으며, 이미 체크가 된 셀프 넘버의 경우는 이후 과정이 동일하므로 캐싱할 수 있다.  따라서 10000개를 모두 체크하여도 시간안에 들어온다.

3. 2xn 타일링: https://www.acmicpc.net/problem/11726 

#include <iostream>

using namespace std;

int N;
int cacheOfTiles[10008];

int tiling(int sumOfTiles){
    if(sumOfTiles == N){
        return 1;
    } else if(sumOfTiles > N){
        return 0;
    }
    int &ret = cacheOfTiles[sumOfTiles];
    if(ret != 0)
        return ret % 10007;
    return ret = (tiling(sumOfTiles +1) % 10007 + tiling(sumOfTiles + 2) % 10007) % 10007;
}

int main(){
    cin >> N;
    cout << tiling(0);
    return 0;
}

 O(2^N)인데 좌우 재귀 호출에서 sumOfTiles 값이 많이 겹친다.  겹치는 구간을 캐싱하면 왼쪽 재귀만 돌고 오른쪽 재귀로 들어갈 때 대부분 캐싱된다. 

4. 합이 0인 네 정수: https://www.acmicpc.net/problem/7453 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
    int N;
    vector<int> A1, C1;
    cin >>N;
    vector<int> A,B,C,D;
    for(int i=0; i < N; i++){
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        A.push_back(a);
        B.push_back(b);
        C.push_back(c);
        D.push_back(d);
    }
    for(int i = 0 ; i < N; i++){
        for(int j = 0; j < N; j++){
            A1.push_back(A[i] + B[j]);
            C1.push_back(C[i] + D[j]);
        }
    }
    sort(A1.begin(), A1.end());
    long long int ans = 0;
    for(int c : C1){
        auto r = equal_range(A1.begin(), A1.end(), -c);
        ans += r.second - r.first;
    }
    cout << ans << endl;
    return 0;
}

 1600 0000이면 정렬했을 때 1600 0000 * log(1600 0000, 2)가 나와서 넘어가지 않을까 했었는데 단순히 1초를 1억으로 퉁치면 안된다.  정렬은 O(nlogn) 이므로 2천만 입력까지 1초에 풀 수 있다.  equal_range는 O(2*log(distance))함수로 시간복잡도로 보건데 binary tree로 n개의 같은 값을 찾는 함수로 보인다.  정렬이 가장 큰 비중을 차지하는데 1600만의 입력을 처리하므로 1초안에 처리할 수 있으며, 문제의 제한시간은 2초이므로 통과된다.  

5. 피자 판매: https://www.acmicpc.net/problem/2632 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int target;
    cin >> target;
    int pn1, pn2, pSum = 0;
    cin >> pn1 >> pn2;
    vector<int> p1, p2, extendedP1, extendedP2;
    for(int i = 0 ; i < pn1; i++){
        int v;
        cin >> v;
        p1.push_back(v);
    }
    for(int i = 0 ; i < pn2; i++){
        int v;
        cin >> v;
        p2.push_back(v);
    }
    for(int i = 0; i < pn1; i++){
        int j = i + 1;
        pSum = p1[i];
        if(j == pn1) j = 0;
        while(j != i){
            if(pSum <= target){
                extendedP1.push_back(pSum);
            }
            pSum += p1[j++];
            if(j == pn1) j = 0;
        }
    }
    extendedP1.push_back(pSum);
    sort(extendedP1.begin(), extendedP1.end()); // for equal_range, O(N log N)
    for(int i = 0; i < pn2; i++){
        int j = i + 1;
        pSum = p2[i];
        if(j == pn2) j = 0;
        while(j != i){
            if(pSum <= target){
                extendedP2.push_back(pSum);
            }
            pSum += p2[j++];
            if(j == pn2) j = 0;
        }
    }
    extendedP2.push_back(pSum);
    long long int ans = 0;
    for(auto ep2: extendedP2){ // N
        if(target - ep2 > 0){
            auto er = equal_range(extendedP1.begin(), extendedP1.end(), target - ep2); // 2*(log N)
            ans += (er.second - er.first);
        } else if(target - ep2 == 0){
            ans += 1;
        }
    }
    auto er = equal_range(extendedP1.begin(), extendedP1.end(), target); // 2*log(N)
    ans += (er.second - er.first);
    cout << ans << "\n";
    return 0;
}

 겹치는 코드가 있어서 약간 길다.  피자를 1000가지로 나눌 수 있으므로 최대 1000 *998 + 1가지의 경우의 수가 나온다.  그 경우를 모두 구해주고 한 가지만 정렬해서 equal_range로 target을 찾는다.  이때 sorting과 linear * equal_range[O(2*log(N))]에서 가장 많은 시간이 걸리지만 약 1천만개의 샘플이라 두 가지 모두 1초에 크게 못 미친 시간이 걸린다.  따라서 2초 제한 시간을 통과한다.

6. 두 배열의 합: https://www.acmicpc.net/problem/2143 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int target;
    vector<int> mv, nv, extendedMv, extendedNv;
    cin >>target;
    int M, N;
    cin >> M;
    for(int i = 0 ; i < M; i++){
        int a;
        cin >> a;
        mv.push_back(a);
    }
    cin >> N;
    for(int i = 0 ; i < N; i++){
        int a;
        cin >> a;
        nv.push_back(a);
    }
    for(int i = 0 ; i < M; i++){
        int pSum = 0;
        for(int j = i; j < M; j++){
            pSum += mv[j];
            extendedMv.push_back(pSum);
        }
    }
    for(int i = 0 ; i < N; i++){
        int pSum = 0;
        for(int j = i; j < N; j++){
            pSum += nv[j];
            extendedNv.push_back(pSum);
        }
    }
    sort(extendedMv.begin(), extendedMv.end());
    long long int ans = 0;
    for(auto e: extendedNv){
        auto pe = equal_range(extendedMv.begin(), extendedMv.end(), target - e);
        ans += pe.second - pe.first;
    }
    cout << ans << endl;
    return 0;
}

 5번과 동일한 문제다.  유일하게 주의해야 하는게 integer overflow인데 T가 10억이고 1,000,000 * 1000이 최대값이므로 두 개를 더해도 2^31(=2,147,483,648)보다 작다.  따라서 정수형을 사용해도 된다.  다만, ans에서는 10,000,000 * 10,000,000이 들어 올 수도 있다고 거칠게 생각하면 long long int로 할 때 integer overflow가 발생할 일이 없다.

7. LCA: https://www.acmicpc.net/problem/11437 

#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>

using namespace std;
int levels[50001];
int parents[50001];
int visited[50001];

int main(){
    int N;
    scanf("%d", &N);
    int src, dst;
    vector<vector<int> > nodes(50001);
    for(int i = 0 ; i < N - 1; i++){
        scanf("%d %d", &src, &dst);
        nodes[src].push_back(dst);
        nodes[dst].push_back(src);
    }
    queue<int> que;
    que.push(1);
    levels[1] = visited[1] = 1;
    while(!que.empty()){
        int t = que.front();
        que.pop();
        for(auto v : nodes[t]){
            if(visited[v]) continue;
            parents[v] = t;
            levels[v] = levels[t] + 1;
            que.push(v);
            visited[v] = 1;
        }
    }
    int cases;
    scanf("%d", &cases);
    while(cases--){
        int v1, v2;
        scanf("%d %d", &v1, &v2);
        if(levels[v1] < levels[v2]) swap(v1, v2);
        while(levels[v1] != levels[v2]){
            v1 = parents[v1];
        }
        while(v1 != v2){
            v1 = parents[v1];
            v2 = parents[v2];
        }
        printf("%d\n", v1);
    }
    return 0;
}

 parent와 level(=depth)를 사용해서 공통 조상을 찾는 문제다.  입출력 값이 많아서 cin, cout으로는 시간초과가 나고 cin 입력을 빠르게 하는 코드를 사용해도 시간초과가 난다.

8. 정점들의 거리: https://www.acmicpc.net/problem/1761 

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

class Edge{
public:
    int d, w;
    Edge(int d, int w):d(d), w(w){}
};

int parents[40001];
int visited[40001];
int depth[40001];
int weights[40001];

int main(){
    int N;
    scanf("%d", &N);
    vector<vector<Edge> > edges(40001);
    for(int i=0; i < N - 1; i++){
        int s, d, w;
        scanf("%d %d %d", &s, &d, &w);
        edges[s].push_back(Edge(d, w));
        edges[d].push_back(Edge(s, w));
    }
    queue<Edge> que;
    visited[1] = 1;
    depth[1] = 1;
    que.push(Edge(1, 0));
    while(!que.empty()){
        Edge baseNode = que.front();
        int baseIdx = baseNode.d;
        que.pop();
        for(auto iterNode : edges[baseIdx]){
            int iterIdx = iterNode.d;
            int iterW = iterNode.w;
            if(visited[iterIdx]) continue;
            weights[iterIdx] = iterW;
            parents[iterIdx] = baseIdx;
            depth[iterIdx] = depth[baseIdx] + 1;
            visited[iterIdx] = 1;
            que.push(iterNode);
        }
    }
    int cases;
    scanf("%d", &cases);
    while(cases--){
        long long int ans = 0;
        int n1, n2;
        scanf("%d %d", &n1, &n2);
        if(depth[n1] > depth[n2]){
            swap(n1, n2);
        }
        while(depth[n2] != depth[n1]){
            ans += weights[n2];
            n2 = parents[n2];
        }
        while(n2 != n1){
            ans += (weights[n1] + weights[n2]);
            n2 = parents[n2];
            n1 = parents[n1];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

 weight를 Edge class에 저장하고 이를 parents나 depth와 같은 방법으로 참조해서 ans에 더해준다.