AtCoder ABC 265 풀이

A. 

1개살때 X원, 3개살때 Y원이 들때 N개살때 최소비용을 구하는 문제입니다. 

우선, Y가 3X이상이면 그냥 다 1개씩 사면 됩니다. 

그 외의 경우엔 3개씩 최대한 묶고 남은걸 1개씩 사주면 됩니다. 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int x, y, N;
    cin >> x >> y >> N;
    if (y >= 3 * x) {
        cout << N * x;
    }
    else {
        cout << x * (N % 3) + y * (N - N % 3) / 3;
    }
}

 

B. 

시간제한이 주어지고 그 전에 도달가능성을 묻는 문제입니다. 

우선 보너스 룸은 도착점 전에 있으므로 지나가는게 항상 이득입니다. 

따라서 보너스 룸 M개를 전부 지나고 N에 도달할 수 있는지 구현해주면 됩니다. 

거리의 차는 누적합으로 전처리해서 O(1)에 처리합시다. 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 100010;
ll n, m, t, a[MAX], x[MAX], y[MAX], psum[MAX];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> t;
    for (int i = 1; i < n; i++) {
        cin >> a[i];
        psum[i + 1] = psum[i] + a[i];
    }
    ll time_limit = t;
    x[0] = 1;
    for (int i = 1; i <= m; i++) {
        cin >> x[i] >> y[i];
        time_limit -= (psum[x[i]] - psum[x[i - 1]]);
        if (time_limit > 0) {
            time_limit += y[i];
        }
        else {
            cout << "No";
            return 0;
        }
    }
    ll tt = psum[n] - psum[x[m]];
    time_limit -= tt;
    if (time_limit > 0) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
}

 

C. 

이동순서가 주어질때 외부로 나갈때까지 이동하고, 사이클이 생기면 -1을 출력하는 문제입니다. 

이동순서가 그래프로 주어지므로 dfs 1번으로 답이 결정됩니다. 사이클이 생긴다면 방문한 점을 재방문하는 

경우가 유일합니다. 나머지는 쉽습니다. 

 

#include <bits/stdc++.h>
using namespace std;
int H, W, vis[505][505];
char G[505][505];

bool in(int x, int y) {
    return (x && y && x <= H && y <= W);
}

void dfs(int x, int y, int px, int py) {
    if (vis[x][y]) {
        cout << -1;
        return;
    }
    if (!in(x, y)) {
        cout << px << " "<< py;
        return;
    }
    vis[x][y] = 1;
    if (G[x][y] == 'U') {
        dfs(x - 1, y, x, y);
    }
    if (G[x][y] == 'D') {
        dfs(x + 1, y, x, y);
    }
    if (G[x][y] == 'L') {
        dfs(x, y - 1, x, y);
    }
    if (G[x][y] == 'R') {
        dfs(x, y + 1, x, y);
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);   
    cin >> H >> W;
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            cin >> G[i][j];
        }
    }
    dfs(1, 1, -1, -1);
}

 

D.

적절히 연속된 구간을 잡아서 합이 P,Q,R이 되게 하는 경우가 있는지 묻는 문제입니다. 

시작점 X를 고정하고 이분탐색을 해주면 됩니다. 

 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, p, q, r, x, psum[200005];

bool chk(ll t) {
    return binary_search(psum + 1, psum + n + 1, t);
}

int solve(int x) {
    ll s = psum[x - 1];
    return chk(s + p) && chk(s + p + q) && chk(s + p + q + r);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);   
    cin >> n >> p >> q >> r;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        psum[i] = psum[i - 1] + x;
    }
    for (int x = 1; x <= n; x++) {
        if (solve(x)) {
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
}

 

E.

3방향으로 이동이 가능하고 못지나는 점들이 주어질때 가능한 경로의 수를 찾는 문제입니다. 

못지나는 점의 좌표는  set이나 map으로 관리합니다. 

dp[n][i][j]를 move1을 i번, move2를 j번, move3을 n-i-j번 사용하여 도착하는 경로의 수라고 정의합니다. 

dp[n][i][j]=dp[n-1][i-1][j]+dp[n-1][i][j-1]+dp[n-1][i][j]가 됩니다. 

단, dp[n][i][j]상태에서 만든 결과가 못지나는 점이면 dp[n][i][j]=0으로 바꿔주면 됩니다. 

n과 n-1만 필요하니 토글링도 해줍시다. 

 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, A, B, C, D, E, F;
int dp[2][303][303];
set<pair<ll, ll>>S;
const int mod = 998244353;

bool func(int n, int x, int y) {
    ll nx = A * x + C * y + E * (n - x - y);
    ll ny = B * x + D * y + F * (n - x - y);
    return (S.find({ nx,ny }) != S.end());
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    cin >> A >> B >> C >> D >> E >> F;
    for (int i = 1; i <= m; i++) {
        ll x, y; cin >> x >> y;
        S.insert({ x,y });
    }
    dp[0][0][0] = 1;
    for (int k = 1; k <= n; k++) {
        for (int i = 0; i <= k; i++) {
            for (int j = 0; j <= k; j++) {
                if (i + j > k) continue;
                int ret = 0;
                int t = k % 2;
                if (func(k, i, j))dp[t][i][j] = 0;
                else {
                    if (i >= 1) {
                        ret += dp[1-t][i - 1][j];
                        if (ret > mod)ret -= mod;
                    }
                    if (j >= 1) {
                        ret += dp[1-t][i][j - 1];
                        if (ret > mod)ret -= mod;
                    }
                    ret += dp[1-t][i][j];
                    if (ret > mod)ret -= mod;
                    dp[t][i][j] = ret;
                }
            }
        }
    }
    int ans = 0;
    for (int x = 0; x <= n; x++) {
        for (int y = 0; y <= n; y++) {
            ans += dp[n%2][x][y];
            if (ans > mod) ans -= mod;
        }
    }
    cout << ans;
}

 

F.

 

택시거리 2개가 모두 D이하가 되도록 수열 R의 개수를 찾는 문제입니다. 

O(ND^3)은 쉽지만 최적화가 어렵네요. 풀이는 이후에 올리겠습니다.