3월 차 PS 기록

_Junick·2025년 3월 14일
Problem Solvingps백준코포

PS 기록

목록 보기
1/1

BOJ 23815: 똥게임

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

메인 아이디어

광고를 사용해 단 한 번 건너뛸 수 있고, 어짜피 게이트 하나를 통과하는 것은 그리디가 적용되므로, dp[i][0]dp[i][0]과 dp[i][1]dp[i][1]을 사용해서 점화식을 적자 www

점화식

f(x,s)f(x, s)를 이렇게 정의하자: xx에다가 ss 연산을 적용한 뒤의 값
또한 Si0S_{i0}과 Si1S_{i1}은 각각 ii번째 게이트의 첫 번째 연산과 두 번째 연산이다.

이 때, dp[i][0]dp[i][0]의 점화식은:

dp[i][0]={max⁡{f(dp[i−1][0],Si0),f(dp[i−1][0],Si1),0}if dp[i-1][0] > 00if dp[i-1][0] = 0dp[i][0] = \begin{cases} \max\{f(dp[i-1][0], S_{i0}), f(dp[i-1][0], S_{i1}), 0\} & \text{if dp[i-1][0] > 0} \\ 0 & \text{if dp[i-1][0] = 0} \end{cases}

이렇게 된다.

dp[i][1]dp[i][1]은 조금 복잡하다.

Di1={max⁡{f(dp[i−2][0],Si1),f(dp[i−2][0],Si2)}if dp[i−2][0]>00if dp[i−2][0]=0,Di2={max⁡{f(dp[i−1][1],Si1),f(dp[i−1][1],Si2)}if dp[i−1][1]>00if dp[i−1][1]=0D_{i1}= \begin{cases} \max \{ f(dp[i-2][0], S_{i1}), f(dp[i-2][0], S_{i2}) \} & \text{if $dp[i-2][0] > 0$}\\ 0 & \text{if $dp[i-2][0] = 0$} \end{cases}, \\ D_{i2} = \begin{cases} \max\{f(dp[i-1][1], S_{i1}), f(dp[i-1][1], S_{i2})\} & \text{if $dp[i-1][1] > 0$} \\ 0 & \text{if $dp[i-1][1] = 0$} \end{cases}

이라고 정의됐을 때,

dp[i][1]={max⁡{Di1,Di2,0}if i≥20if i<2dp[i][1] = \begin{cases} \max \{ D_{i1}, D_{i2}, 0 \} & \text{if $i \ge 2$} \\ 0 & \text{if $i < 2$} \end{cases}

이 때, 주의해야 할 점은, NN번째 게이트도 광고로 건너뛸 수 있기 때문에, Si1=Si2="+0"S_{i1}=S_{i2}= \text{"+0"}으로 정의해두고, N+1N+1까지 반복문을 돌아야 한다는 것이다.

얘네들 다 썼으면, dp[N+1][0]=dp[N+1][1]=0dp[N+1][0]=dp[N+1][1]=0일 때 "ddong game", 아니면 저 두 개의 값들 중 최댓값을 출력하면 된다.

정답 코드

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

using namespace std;
using ll = long long;
const int INF = 1e9 + 7;

int N;
int dp[100005][3];
pair <string, string> op[100005];

int eval(int n, const string &op) {
    if(op[0] == '+') {
        return n + (op[1] - '0');
    }
    if(op[0] == '-') {
        return n - (op[1] - '0');
    }
    if(op[0] == '*') {
        return n * (op[1] - '0');
    }
    if(op[0] == '/') {
        return n / (op[1] - '0');
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    dp[0][0] = dp[0][1] = 1;
    op[N+1].fi = op[N+1].se = "+0";
    for(int i = 1; i <= N+1; i++) {
        if(i <= N) cin >> op[i].fi >> op[i].se;
        
        if(dp[i-1][0] > 0) {
            dp[i][0] = max(eval(dp[i-1][0], op[i].fi), eval(dp[i-1][0], op[i].se));
        }
        dp[i][0] = max(0, dp[i][0]);

        if(i >= 2) {
            if(dp[i-2][0] > 0) dp[i][1] = max({dp[i][1], eval(dp[i-2][0], op[i].fi), eval(dp[i-2][0], op[i].se)});
            if(dp[i-1][1] > 0) dp[i][1] = max({dp[i][1], eval(dp[i-1][1], op[i].fi), eval(dp[i-1][1], op[i].se)});
            dp[i][1] = max(0, dp[i][1]);
        }
    }

    int ans = max(dp[N+1][0], dp[N+1][1]);
    if(ans == 0) cout << "ddong game\n";
    else cout << ans << "\n";
    return 0;
}

BOJ 1456: 거의 소수

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

메인 아이디어

보자마자 체 쓰는 아이디어가 떠올랐다. 어짜피 N\sqrt{N}은 10710^{7}이기에 충분하지 않을까.
nn제곱 꼴로 나타내지는 수들의 개수도 별로 없는 것 같다. 그냥 깡구현으로 풀어보자.

풀린다! 근데 오버플로우 조심하자.
체로 우선 10710^{7} 이하인 수들의 소수 여부를 구해주고, 그 소수를 대상으로만 계속 nn제곱을 시켜주면서 A≤pn≤BA \leq p^n \leq B를 만족하면 정답 변수를 하나 증가시켜주는 방식으로 naïve하게 풀 수 있다.
대신 while문에 overflow 조건문을 걸어두자.

정답 코드

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

using namespace std;
using ll = long long;
const int INF = 1e9 + 7;

vector <bool> sieve(10000007);
void letsgosieve() {
    fill(all(sieve), true);
    sieve[0] = sieve[1] = false;
    for(int i = 2; i <= 10000000; i++) {
        if(!sieve[i]) continue;
        for(int j = i+i; j <= 10000000; j += i) {
            sieve[j] = false;
        }
    }
}

ll A, B;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    letsgosieve();

    cin >> A >> B;

    ll ans = 0;
    for(int i = 2; i <= 10000000; i++) {
        if(!sieve[i]) continue;
        ll a = 1LL*i*i;
        while(a <= B) {
            if(A <= a) ans++;
            if(a <= LLONG_MAX / i) a *= i;
            else break;
        }
    }
    cout << ans << "\n";
    return 0;
}

BOJ 28069: 김밥천국의 계단

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

메인 아이디어

일단 N≤KN \leq K면 무조건 김밥을 먹을 수 있습니다. 왜냐하면, 00번째 계단에서 2번째 행동을 남발한 뒤에, 정확히 NN번 더 행동을 할 수 있을 때부터 한 칸씩 계단을 오르면 되기 때문입니다.
또한, 계단을 내려갈 수는 없습니다.
어 잠만 이거 그냥 BFS잖아

네 MLE 받았어요 다시는 나대지 않겠습니다ㅠㅠ

네 AC 받았어요 나댈게요
00번째 계단에서 2번째 행동을 남발한다는 것 기억하시나요? 그걸 일반적인 상황에서 적용시키면, 결국 이 문제는 KK번 이내로 NN번째 계단에 도달하는 문제로 바꿔버릴 수 있습니다.
그럼 MLE 같은 거 없이 그냥 무지성 BFS를 돌리면 됩니다.

정답 코드

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

using namespace std;
using ll = long long;
const int INF = 1e9 + 7;

int N, K;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> K;
    if(N <= K) {
        cout << "minigimbob\n";
        return 0;
    }

    queue <int> q;
    vector <int> dist(N+1, 0);
    
    q.push(1);
    dist[1] = 1;

    while(q.size()) {
        int cur = q.front();
        q.pop();

        if(dist[cur] > K) break;
        if(cur == N) {
            cout << "minigimbob\n";
            return 0;
        }

        if(cur+1 <= N && !dist[cur+1]) {
            q.push(cur+1);
            dist[cur+1] = dist[cur]+1;
        }
        if(cur+cur/2 <= N && !dist[cur+cur/2]) {
            q.push(cur+cur/2);
            dist[cur+cur/2] = dist[cur]+1;
        }
    }
    cout << "water\n";
    return 0;
}

BOJ 1897: 토달기

메인 아이디어

틀린 이유

문제를 잘못 이해해서 글자를 추가한 뒤 나온 단어가 무조건 사전에 있는 단어여야 한다는 사실을 무시한 채 solution을 작성했다.
문제를 잘못 이해해서 그냥 subsequence가 있으면 한 단어 차이로 취급해버린 채 solution을 작성했다.

진짜 해결법은 뭔데?

BFS를 돌리면 된다.
두 단어가 한 단어를 문자열 어딘가에 삽입해서 만들 수 있는 경우; 즉, 한 문자열이 다른 문자열의 subsequence이며 두 문자열의 길이의 차이가 11인 경우, 두 정점을 연결해준다!
그 상태로 원장님이 말씀하신 단어를 시작점으로 한 BFS를 돌리고, BFS가 돌아가는 동안 answer의 업데이트가 필요하면 업데이트를 해준다.

정답 코드

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

using namespace std;
using ll = long long;
const int INF = 1e9 + 7;

int d; string s;
vector <string> v;
vector <vector <int>> adj;
int st = 0;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> d >> s;

    v.resize(d); adj.resize(d);
    for(int i = 0; i < d; i++) {
        cin >> v[i];
    }

    sort(all(v), [&](const string &p, const string &q) {
        return p.length() < q.length();
    });
    
    for(int i = 0; i < d; i++) {
        if(v[i] == s) st = i;
    }

    for(int k = 0; k < d; k++) {
        for(int l = k+1; l < d; l++) {
            string &ks = v[k], &ls = v[l];
            if(ls.length() - ks.length() != 1) continue;

            int idx = 0;
            for(int i = 0; i < ls.length(); i++) {
                if(ks[idx] == ls[i]) idx++;
                if(idx == ks.length()) break;
            }
            if(idx == ks.length()) {
                adj[k].push_back(l);
            }
        }
    }

    string ans = "";
    queue <int> q;
    vector <bool> visited(d, false);
    
    visited[st] = true; q.push(st);
    while(q.size()) {
        int cur = q.front();
        q.pop();

        if(ans.length() < v[cur].length()) ans = v[cur];

        for(int &to : adj[cur]) {
            if(visited[to]) continue;
            q.push(to);
        }
    }
    cout << ans << "\n";
    return 0;
}

BOJ 21772: 가희의 고구마 먹방

메인 아이디어

왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?왜그래요?
왜그래요?

매우 귀찮은 깡구현
가능한 55가지의 움직임 중에서 하나를 골라 백트래킹하자.
510=9 765 6255^{10}=9\,765\,625이기에 충분히 돌아간다. (실제론 저거보다 적다)

정답 코드

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

using namespace std;
using ll = long long;
const int INF = 1e9 + 7;

int R, C, T;
vector <string> mp;

int gx, gy;
int cur = 0;
int ans = 0;

int dx[] = {0, 0, 1, -1, 0};
int dy[] = {1, -1, 0, 0, 0};

void backtracking(int node, int x, int y) {
    if(node >= T) {
        ans = max(ans, cur);
        return;
    }

    for(int k = 0; k < 5; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
        if(mp[nx][ny] == '#') continue;

        bool goguma = mp[nx][ny] == 'S';
        if(goguma) {
            cur++;
            mp[nx][ny] = '.';
        }
        backtracking(node+1, nx, ny);
        if(goguma) {
            cur--;
            mp[nx][ny] = 'S';
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> R >> C >> T;
    
    mp.resize(R);
    for(int i = 0; i < R; i++) {
        cin >> mp[i];
        for(int j = 0; j < C; j++) {
            if(mp[i][j] == 'G') gx = i, gy = j;
        }
    }

    backtracking(0, gx, gy);

    cout << ans << "\n";
    return 0;
}

BOJ 1354: 무한 수열 2

메인 아이디어

고 뭐고 없고 그냥 무지성 메모제이션 유사 피보나치 함수 구현

정답 코드

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

using namespace std;
using ll = long long;
const int INF = 1e9 + 7;

ll N, P, Q, X, Y;
unordered_map <ll, ll> dp;

ll f(ll i) {
    if(i <= 0) return 1;
    if(dp.count(i)) return dp[i];

    return dp[i] = f(i/P - X) + f(i/Q - Y);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> P >> Q >> X >> Y;
    cout << f(N) << "\n";
    return 0;
}

BOJ 12887: 경로 게임

메인 아이디어

무지성 BFS! 근데 좀 구현을 복잡하게 한 감이 있다.
그리드의 가장 왼쪽부터 가장 오른쪽까지의 최단 경로를 SS라고 하고, 그리드에 있는 '#'(벽)의 개수를 WW라고 하자. 그럼 정답은

ans=2M−S−W\text{ans}=2M-S-W

가 된다. 여기서 최단 경로는 BFS 하나로 구할 수 있어서 그냥 BFS 문제인 🤣

정답 코드

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

using namespace std;
using ll = long long;
const int INF = 1e9 + 7;

int dx[] = {0, 1, -1};
int dy[] = {1, 0, 0};

int M;
vector <string> mp(2);
vector <vector <int>> dist;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int ans = 0;

    cin >> M;
    for(int i = 0; i < 2; i++) {
        cin >> mp[i];
        for(char &c : mp[i]) if(c == '#') ans++;
    }

    int ans2 = INF;
    queue <pair <int, int>> q;
    if(mp[0][0] == '.') {
        dist = vector <vector <int>> (2, vector<int>(M, INF));
        while(q.size()) q.pop();

        q.push({0, 0});
        dist[0][0] = 1;
        while(q.size()) {
            auto [x, y] = q.front();
            q.pop();

            for(int k = 0; k < 3; k++) {
                int nx = x + dx[k], ny = y + dy[k];
                if(nx < 0 || nx >= 2 || ny < 0 || ny >= M) continue;
                if(mp[nx][ny] == '#') continue;
                if(dist[nx][ny] != INF) continue;

                q.push({nx, ny});
                dist[nx][ny] = dist[x][y] + 1;
            }
        }
        ans2 = min({ans2, dist[0][M-1], dist[1][M-1]});
    }
    if(mp[1][0] == '.') {
        dist = vector <vector <int>> (2, vector<int>(M, INF));
        while(q.size()) q.pop();

        q.push({1, 0});
        dist[1][0] = 1;
        while(q.size()) {
            auto [x, y] = q.front();
            q.pop();

            for(int k = 0; k < 3; k++) {
                int nx = x + dx[k], ny = y + dy[k];
                if(nx < 0 || nx >= 2 || ny < 0 || ny >= M) continue;
                if(mp[nx][ny] == '#') continue;
                if(dist[nx][ny] != INF) continue;

                q.push({nx, ny});
                dist[nx][ny] = dist[x][y] + 1;
            }
        }
        ans2 = min({ans2, dist[0][M-1], dist[1][M-1]});
    }
    cout << 2*M - ans - ans2 << "\n";
    return 0;
}

BOJ 28471: W키가 빠진 성원이

메인 아이디어

blobnom에만 BFS가 몇 문제나 나오는 거임??
목적지에서 시작해서 밑으로 가는 것만 제외해주면 됨
visited[i][j]가 true인 것들 개수 세서 출력 (목적지 제외)

정답 코드

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

using namespace std;
using ll = long long;
const int INF = 1e9 + 7;

int dx[] = {0, 0, -1, -1, -1, 1, 1};
int dy[] = {1, -1, 0, -1, 1, -1, 1};

int N;
vector <string> mp;
int sx = 0, sy = 0;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    mp.resize(N);
    for(int i = 0; i < N; i++) {
        cin >> mp[i];
        for(int j = 0; j < N; j++) {
            if(mp[i][j] == 'F') sx = i, sy = j;
        }
    }

    queue <pair <int, int>> q;
    vector <vector <bool>> visited(N, vector <bool>(N, false));

    q.push({sx, sy});
    visited[sx][sy] = true;
    while(q.size()) {
        auto [x, y] = q.front();
        q.pop();

        for(int k = 0; k < 7; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if(visited[nx][ny]) continue;
            if(mp[nx][ny] == '#') continue;

            visited[nx][ny] = true;
            q.push({nx, ny});
        }
    }

    int ans = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            ans += visited[i][j];
        }
    }
    cout << ans - 1 << "\n";
    return 0;
}

BOJ 30089: 새로운 문자열 만들기

메인 아이디어

뭐 문자열의 접미사(suffix) 중에 팰린드롬인 것 중에 가장 긴 거를 찾는 문제인가 했는데, ∣S∣≤20|S| \leq 20이라서 그냥 무지성으로 브포로 풀면 된다.
복잡하게 생각하지 않는 습관을 들이자.

정답 코드

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

using namespace std;
using ll = long long;

bool satisfies(string X, const string &S) {
    bool f1 = (X.substr(0, S.length()) == S);

    reverse(all(X));
    bool f2 = (X.substr(0, S.length()) == S);

    return (f1 && f2);
}

void solve(const int &tc) {
    string S; cin >> S;

    string cS = S;
    reverse(all(cS));

    string ans = S + cS;
    for(int i = 0; i <= S.length(); i++) {
        string tmp = S + cS.substr(i);
        if(satisfies(tmp, S)) ans = tmp;
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T; cin >> T;
    for(int i = 1; i <= T; i++) solve(i);
    return 0;
}

BOJ 30090: 백신 개발

메인 아이디어

일단 1≤N≤91 \leq N \leq 9고 1≤∣S∣≤101 \leq |S| \leq 10이라서 아싸 무지성 브포 돌려야지 했는데...
3틀을 해버렸다. 왜인지 봤더니 최솟값이 아니라 최댓값을 구하고 있었다. 이런 뻘짓만 안했으면 좋겠는데...

정답 코드

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

using namespace std;
using ll = long long;
const int INF = 1e9 + 7;

int N;
vector <string> v;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    
    v.resize(N);
    for(int i = 0; i < N; i++) cin >> v[i];

    sort(all(v));
    
    int ans = INF;
    do {
        string s = v[0];
        bool fail = false;
        for(int i = 1; i < v.size(); i++) {
            int n = min(s.length(), v[i].length());
            int j;
            for(j = n; j >= 1; j--) {
                string s1 = s.substr(s.length() - j);
                string s2 = v[i].substr(0, j);
                if(s1 == s2) {
                    break;
                }
            }
            if(j == 0) {
                fail = true;
                break;
            }
            s += v[i].substr(j);
        }
        if(fail) continue;
        ans = min(ans, int(s.length()));
    } while(next_permutation(all(v)));
    cout << ans << "\n";
    return 0;
}

BOJ 31995: 게임말 올려놓기

메인 아이디어

너무쉬운조합론문제

정답 코드

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

using namespace std;
using ll = long long;
const int INF = 1e9 + 7;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M; cin >> N >> M;
    cout << max(0, ((N - 2) * 2 + 2) * (M-1));
    return 0;
}

profile
_Junick
asdf 🔥

0개의 댓글