백준: Class 5 - 17404, 20040, 1644

</br> 클래스 5 계속
</br>

17404: RGB거리 2

https://www.acmicpc.net/problem/17404

int func(int r, int g, int b){
    dp[0][0] = rgb[0][0] + r;
    dp[0][1] = rgb[0][1] + g;
    dp[0][2] = rgb[0][2] + b;
    for(int i = 1; i < n; i++){
        dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + rgb[i][0];
        dp[i][1] = min(dp[i-1][2], dp[i-1][0]) + rgb[i][1];
        dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + rgb[i][2];
    }
    r = 1001 - r;
    g = 1001 - g;
    b = 1001 - b;
    return min({dp[n-1][0]+r, dp[n-1][1]+g, dp[n-1][2]+b});
}

// in main()
    for(int i = 0; i < n; i++){
        int r, g, b;
        cin >> r >> g >> b;
        rgb[i][0] = r;
        rgb[i][1] = g;
        rgb[i][2] = b;
    }
    int r = func(0, 1001, 1001);
    int g = func(1001, 0, 1001);
    int b = func(1001, 1001, 0);
    cout << min({r, g, b}) << endl;

전 포스트(1149: RGB거리, https://cyj893.github.io/algorithm/Algorithm9_2/)에서 진화한 문제
다 똑같은데, 첫번째와 n번째가 겹치면 안 된다.
따라서 처음이 R일 때, G일 때, B일 때를 나눠 주면 된다.
처음이 R이면, 마지막 dp에서 R일 때를 제외하고 min값을 고르면 된다. G와 B일 때도 마찬가지이고, 이 세 값들 중 min값을 고르면 답이다.
처음에 R을 고르게 하기 위해, 처음 dp의 G와 B에 1001을 더해서 걔네를 안 골라지게 했다.
그리고 답을 고를 때는 R을 피하게 하기 위해, 마지막 dp의 R에 1001을 더해서 걔를 안 골라지게 했다

ex) 백준 예제
3
26 40 83
49 60 57
13 89 99

dp(처음이 R)
26 1041 1084
1090 86 83
96 172 185  < R을 제외한 min값 고르기
ans: 172

dp(처음이 G)
1027 40 1084
89 1087 97
110 178 188  < G를 제외한 min값 고르기
ans: 110

dp(처음이 B)
1027 1041 83
132 143 1084
156 221 231  < B를 제외한 min값 고르기
ans: 156

min(172, 110, 156) = 110

</br>

20040: 사이클 게임

https://www.acmicpc.net/problem/20040

struct UnionFind{
    vector<int> parent, ran;
    UnionFind(int n) : parent(n), ran(n, 1){
        for(int i = 0; i < n; i++){
            parent[i] = i;
        }
    }
    int f(int u){
        if( u == parent[u] ) return u;
        return parent[u] = f(parent[u]);
    }
    bool merg(int u, int v){
        u = f(u); v = f(v);
        if( u == v ) return false;
        if( ran[u] > ran[v] ) swap(u, v);
        parent[u] = v;
        ran[v] += ran[u];
        ran[u] = 0;
        return true;
    }
};

// in main()
    UnionFind uf = UnionFind(n);
    int ans = 0;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        if( !uf.merg(a, b) ){
            ans = i+1;
            break;
        }
    }
    cout << ans << endl;

또 union find 문제다
사실 완벽히 외운 줄 알았는데 merg()에 u = f(u); v = f(v);를 u = parent[u]; v = parent[v];로 잘못 써서 한 번 틀렸다 부끄럽군
이제 정말 다 외웠다
</br>

1644: 소수의 연속합

https://www.acmicpc.net/problem/1644

    if( n == 1 ){
        cout << 0 << endl;
        return 0;
    }
    primes[0] = 1;
    primes[1] = 1;
    for(int i = 2; i <= n; i++){
        if( primes[i] ) continue;
        p.push_back(i);
        for(int j = 2; j*i <= n; j++){
            primes[j*i] = 1;
        }
    }

    int ans = 0;
    if( primes[n] == 0 ) ans++;
    int l = 0, r = 1;
    int sum = p[0] + p[1];
    while( l < r && r < p.size() ){
        if( sum == n ){
            ans++;
            r++;
            sum += p[r];
        }
        else if( sum < n ){
            r++;
            sum += p[r];
        }
        else{
            sum -= p[l];
            l++;
        }
    }
    cout << ans << endl;

이제 이런 비슷한 문제는 많이 봐서 바로 투 포인터구나 싶네
소수들을 구해서 벡터에 넣는다. 당연히 에라토스테네스의 체
그 다음 구간합을 구하는 거니까 그 벡터를 투 포인터로 찾으면 된다
현재 구간합이 n과 같으면 경우의 수를 추가하고, 다음으로 넘어가야 하니 r을 오른쪽으로 넘긴다
구간합이 n보다 작으면 역시 r을 오른쪽으로 넘겨 합을 크게 한다.
구간합이 n보다 크면 l을 오른쪽으로 넘겨 합을 작게 한다.
</br>

---

325문제를 풀고 학교 랭킹 48등이 되었다
정답률은 57.319%다 계속 틀렸다가 한 번에 맞췄다가 해서 왔다리 갔다리
지금은 8월 21일 0시 12분
</br>