2022.09.24 PS 일지 (BOJ 2206, 16681, 2169, 2515, 4716, 1994)

카카오 코딩 테스트 풀이를 작성했다. 마지막 문제 빼고는 전반적으로 내가 들었던 예전 카카오 난이도보다 낮은 것 같았다.

마지막 문제는 그래도 골드 상위는 될 것 같았다. 아니면 플래 하위까지도 가능할지도 모르겠다.

암튼... 작성하기 귀찮다.

 

골드 6문제 세트를 200분으로 잡고 돌았다.

35분 남기고 전부 풀어서 다행이다.

사실 점점 시간이 늦어져서 마지막 두 문제는 졸면서 푼 것 같다.

 

벽 부수고 이동하기

단순히 BFS 두 번 돌리고 고려하면 된다. 17분 정도 걸렸다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

const int N = 1003, M = N;
int n, m;
bool b[N][M];
int Ds[N][M], De[N][M];

const ii d4[] {{0,1},{1,0},{0,-1},{-1,0}};
const ii d8[] {{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
bool out(int x, int y) {return 1 > x or x > n or 1 > y or y > m;}

void bfs(int x, int y, int dist[N][M]) {
    queue<ii> q;
    bool visited[N][M] = {0,};
    visited[x][y] = true;
    fill(dist[0],dist[N],1e9);
    dist[x][y] = 1;
    q.push({x,y});
    while (not empty(q)) {
        auto [x,y] = q.front(); q.pop();
        for (auto [dx,dy] : d4) {
            int r = x+dx, c = y+dy;
            if (out(r,c)) continue;
            if (b[r][c]) continue;
            if (visited[r][c]) continue;
            visited[r][c] = true;
            dist[r][c] = dist[x][y]+1;
            q.push({r,c});
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    rep(i,1,n) rep(j,1,m) {
        char c; scanf(" %c ",&c);
        b[i][j] = c-'0';
    }
    bfs(1,1,Ds), bfs(n,m,De);
    int answer = 1e9;
    mup(answer,Ds[n][m]);
    rep(i,1,n) rep(j,1,m) if (b[i][j]) {
        int s = 1e9, e = 1e9;
        for (auto [x,y] : d4) {
            if (out(i+x,j+y)) continue;
            if (b[i+x][j+y]) continue;
            mup(s,Ds[i+x][j+y]);
            mup(e,De[i+x][j+y]);
        }
        mup(answer,s+e+1);
    }
    if (answer == int(1e9)) puts("-1");
    else printf("%d",answer);
}

 

등산

단순히 다익스트라 두 번 돌리고 고려하면 된다.

하산할 때 등호를 반대로 돌리고 고려해야 한다고 착각해서 함수에 비교 함수 파라미터까지 넣어가면서 했다가 등호 방향이 똑같다는 걸 나중에 알아서 좀 시간이 지체되었다.

36분 정도 걸린 것 같다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

const int N = 1e5+3, M = 2e5+3;
int n, m;
ll d, e;
ll h[N], Ds[N], De[N];
vector<pair<int,ll>> adj[N];

void djikstra(int x, ll dist[N]) {
    fill(dist,dist+N,1e14), dist[x] = 0;
    priority_queue<pair<ll,int>> pq;
    pq.push({0,x});
    while (not empty(pq)) {
        auto [d,a] = pq.top(); pq.pop(); d = -d;
        if (d != dist[a]) continue;
        for (auto [b,w] : adj[a]) {
            if (dist[b] > d+w and h[b] > h[a]) {
                dist[b] = d+w;
                pq.push({-dist[b],b});
            }
        }
    }
}

int main() {
    scanf("%d %d %lld %lld", &n, &m, &d, &e);
    rep(i,1,n) scanf("%lld", &h[i]);
    rep(i,1,m) {
        int a, b, w;
        scanf(" %d %d %d ", &a, &b, &w);
        adj[a].push_back({b,w});
        adj[b].push_back({a,w});
    }
    djikstra(1,Ds), djikstra(n,De);
    
    ll answer = -1e14;
    rep(i,2,n-1) {
        Mup(answer,h[i]*e-(Ds[i]+De[i])*d);
    }
    if (answer == -1e14) puts("Impossible");
    else printf("%lld", answer);
}

 

로봇 조종하기

그냥 DP에 살짝 누적 max를 해줘서 시간을 줄이면 된다. 이상하게 구현이 꼬여서 시간이 오래 걸렸다.

체감보다 훨씬 오래 걸렸는데 54분이나 걸렸다..!! 잘못 잰 거 아닌가 의심도 된다...

UPD: 스코어보드 보니까 20분 걸렸다. 뽀로로와 함께하는 시계 보기를 다시 공부해야겠다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

const int N = 1003, M = 1003;
int n, m;
ll b[N][M], s[N][M];

int main() {
    scanf("%d %d", &n, &m);
    rep(i,1,n) rep(j,1,m) {
        scanf("%lld", &b[i][j]);
    }
    fill(s[0]+2,s[N],-1e9);
    auto c = s[1];
    rep(i,1,n) {
        rep(j,1,m) {
            ll v = s[i-1][j]+b[i][j];
            for (int k = j; k >= 1; v += b[i][--k]) {
                Mup(s[i][k],v);
            }
            v = s[i-1][j]+b[i][j];
            for (int k = j; k <= m; v += b[i][++k]) {
                Mup(s[i][k],v);
            }
        }
    }
    printf("%lld", s[n][m]);
}

 

전시장

그나마 생각할 거리가 있는 문제였던 것 같다. 누적 max에 이진 탐색을 함께 쓰면 된다.

25분 걸렸다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

const int N = 3e5+3;
int n, s, h[N];
ll c[N];
pair<int,ll> a[N];
ll dp[N], pfx[N];

int main() {
    scanf("%d %d", &n, &s);
    rep(i,1,n) {
        scanf("%d %lld", &a[i].first, &a[i].second);
    }
    sort(a+1,a+n+1);
    for (int i = n, j; i >= 1; --i) {
        for (j = i-1; j >= 1; --j) {
            if (a[i].first != a[j].first) break;
            a[j].second = a[i].second;
        }
        i = j+1;
    }
    n = unique(a+1,a+n+1)-a-1;
    rep(i,1,n) h[i] = a[i].first, c[i] = a[i].second;
    
    rep(i,1,n) {
        int a = 1, b = i-1;
        while (a <= b) {
            int m = (a+b)/2;
            if (h[i]-h[m] >= s) a = m+1;
            else b = m-1;
        }
        Mup(dp[i], pfx[b]+c[i]);
        Mup(dp[i], pfx[i-1]);
        
        pfx[i] = max(dp[i],pfx[i-1]);
    }
    printf("%lld", pfx[n]);
}

 

풍선

그냥 하면 된다. 왜 골드 1인지는 잘 모르겠다.

38분 걸렸다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

const int N = 1003;
int n, a, b;
struct T {
    int k, a, b;
} team[N];

int main() {
    while (1)
    {
        scanf("%d %d %d", &n, &a, &b);
        if (n == 0) break;
        rep(i,1,n) {
            scanf("%d %d %d", &team[i].k, &team[i].a, &team[i].b);
        }
        sort(team+1,team+n+1,[](T &x, T &y) {
            return abs(x.a-x.b) > abs(y.a-y.b);
        });
        ll answer = 0;
        rep(i,1,n) {
            if (team[i].a <= team[i].b and a > 0) {
                int d = min(team[i].k,a);
                answer += d * team[i].a;
                a -= d, team[i].k -= d;
            }
            if (team[i].b <= team[i].a and b > 0) {
                int d = min(team[i].k,b);
                answer += d * team[i].b;
                b -= d, team[i].k -= d;
            }
        }
        rep(i,1,n) {
            if (a > 0) {
                answer += team[i].k * team[i].a;
                a -= team[i].k;
            }
            if (b > 0) {
                answer += team[i].k * team[i].b;
                b -= team[i].k;
            }
        }
        printf("%lld\n", answer);
    }
}

 

등차수열

사실 비슷한 문제를 풀어봤다. 처음에는 조화수열의 합 시간 복잡도를 이용하려고 했는데 잘 안 되길래 DP로 했다.

28분 걸렸다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

const int N = 2003;
int n, a[N];
map<int,int> idx, cnt;
int dp[N][N];

int main() {
    scanf("%d", &n);
    rep(i,1,n) {
        scanf("%d", &a[i]);
        cnt[a[i]]++;
        dp[i][i] = 1;
    }
    int answer = 1;
    sort(a+1,a+n+1);
    rep(i,1,n) idx[a[i]] = i;
    rep(i,1,n) rep(j,i+1,n) Mup(answer,dp[j][i] = 2);
    vector<ll> d;
    rep(i,1,n) rep(j,i+1,n) if (idx.count(2*a[j]-a[i])) {
        int k = idx[2*a[j]-a[i]];
        if (i == k or j == k) continue;
        Mup(dp[k][j],dp[j][i]+1);
        Mup(answer,dp[k][j]);
    }
    for (auto [k,v] : cnt) Mup(answer,v);
    printf("%d", answer);
}