25/01/08 백준일지

32715

처음 읽고 든 생각: 모든 색칠된 좌표를 큐에 넣고 재귀로 해결하면 되지 않을까 생각함. 다만 이러면 시간초과가 확정적이었음

태그를 까보니 Pfx가 있었다. 이게 누적합이라고?라는 생각만 들었는데 곰곰히 생각해보니 pfx로 직선 길이를 쉽게 파악할 수 있음을 깨닳고 바로 코드를 짜서 AC

#include <bits/stdc++.h>

using namespace std;

int pfxx[2550][2550];
int pfxy[2550][2550];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    int k; cin >> k;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            int x; cin >> x;
            pfxy[i][j] = pfxy[i - 1][j] + x;
            pfxx[i][j] = pfxx[i][j - 1] + x;
        }
    }
    int cnt = 0;
    for(int i = k + 1; i <= n - k; i++){
        for(int j = k + 1; j <= m - k; j++){
            if(pfxx[i][j + k] - pfxx[i][j - k - 1] == k * 2 + 1 && pfxy[i + k][j] - pfxy[i - k - 1][j] == k * 2 + 1) cnt++;
        }
    }
    cout << cnt << "\n";
    return 0;
}

23325

처음 읽고 든 생각: 이걸 경우를 어떻게 쪼개야하나…..
태그를 보니 DP가 있었다. 근데 아무리 머리를 굴려봐도 한칸한칸씩 읽어서는 답이 안보였다. 묶어서 경우를 나눠야하나 싶었는데 이게 맞는 접근이었다. 그래서 코드를 짜고 몇번의 오류수정 끝에 AC

#include <bits/stdc++.h>

using namespace std;

int dp[200200];

int conv(char c){
    if(c == '+') return 10;
    else return 1;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string s; cin >> s;
    fill(dp, dp + 200200, -(1<<30));
    dp[0] = conv(s[0]);
    if(s[0] == '+' && s[1] == '-'){
        dp[1] = 11;
    }
    for(int i = 2; i < s.size(); i++){
        if(s[i - 1] == '+') dp[i] = max(dp[i], dp[i - 2] + conv(s[i]));
        else dp[i] = max(dp[i], dp[i - 2] - conv(s[i]));
        if(i == 2) continue;
        if(s[i] == '-' && s[i - 1] == '+'){
            if(s[i - 2] == '+') dp[i] = max(dp[i], dp[i - 3] + 11);
            else dp[i] = max(dp[i], dp[i - 3] - 11);
        }
    }
    cout << dp[s.size() - 1];
    return 0;
}

24892

수학 + 모듈러 연산 문제
최댓값이 되는 경우는 등간격으로 쪼갤 때가 최댓값이 된다.(by 직관)
고등학생때 배웠던 이차함수의 넓이공식을 잘 이용하여 식을 세우자
모듈러 역원에 대하여 공부를 좀 더 해야겠다.

#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007

using namespace std;

ll power_mod(ll a, ll b){
    ll res = 1;
    a %= mod;
    while(b > 0){
        if(b & 1LL) res = (res * a) % mod;
        a = a * a % mod;
        b >>= 1LL;
    }
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, a, b; cin >> n >> a >> b;
    ll dif = b - a;
    ll sum = (pow(n, 3) - n) * pow(dif, 3);
    ll dow = pow(n , 3) * 6;
    ll tmp = gcd(sum, dow);
    sum /= tmp; dow /= tmp;
    cout << (sum * power_mod(dow, mod - 2)) % mod;
    return 0;
}   

17943

간단한 누적합 XOR 문제
0 xor n = n을 떠올리고 누적합 배열을 만들고 잘 풀어보자

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, q; cin >> n >> q;
    vector<int> pfx(n);
    for(int i = 1; i < n; i++){
        cin >> pfx[i];
        pfx[i] ^= pfx[i - 1];
    }
    while(q--){
        int ca; cin >> ca;
        if(ca){
            int a, b, c; cin >> a >> b >> c;
            int ans = pfx[b - 1] ^ pfx[a - 1] ^ c;
            cout << ans << "\n";
        }else{
            int a, b; cin >> a >> b;
            int ans = pfx[b - 1] ^ pfx[a - 1];
            cout << ans << "\n";
        }
    }
    return 0;
}

14907

분명 단순한 위상정렬 + 메모이제이션 문제일줄 알고 싱글벙글 들어갔는데….. 입출력이 시간을 이리 잡아먹을줄..
대신 지식이 늘었습니다. c++에서도 구분자를 기준으로 슬라이싱이 가능하네요
이문제는 분명 입출력때문에 골드2인게 틀림없습니다.

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

using namespace std;

vector<int> adj[26];
vector<int> deg(26);
vector<int> iadj[26];
vector<int> dp(26);
vector<int> cost(26);

int ch(char n){
    return n - 'A';
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string s; queue<int> q;
    while(getline(cin, s)){
        vector<string> tmp;
        stringstream ss(s);
        string t;
        while(getline(ss, t, ' ')) tmp.push_back(t);
        cost[ch(tmp[0][0])] = stoi(tmp[1]);
        if(tmp.size() == 2){
            q.push(ch(tmp[0][0]));
            dp[ch(tmp[0][0])] = stoi(tmp[1]);
        }else{
            for(char c : tmp[2]){
                adj[ch(c)].push_back(ch(tmp[0][0]));
                deg[ch(tmp[0][0])]++;
                iadj[ch(tmp[0][0])].push_back(ch(c));
            }
        }
    }
    while(q.size()){
        int u = q.front(); q.pop();
        for(auto v : adj[u]){
            deg[v]--;
            if(deg[v] == 0){
                for(auto i : iadj[v]){
                    dp[v] = max(dp[v], dp[i]);
                }
                dp[v] += cost[v];
                q.push(v);
            }
        }
    }
    cout << *max_element(dp.begin(), dp.end());
    return 0;
}