2026-02-22 문제풀이

35293 멘헤라

풀이

먼저 4.5를 두번 더하면 9도가 되니까 4.5를 사용하는건 한 번 또는 0번이다. 그리고 소수점에 5나 0 이외의 수가 있다면 만들 수 없다.

이제 모든 수를 다 만들 수 있다고 생각하고 문제를 보면 최단거리 bfs문제와 비슷해진다. 9, 7, -2를 가지고 그래프 탐색을 진행하면 된다.

그러니까 대충 9의 배수인 900으로 나눈 나머지까지 탐색하고 하면 될 것이다. -900 ~ 900 까지 최단거리를 직접구하고 N에서 900을 나눈 나머지로 답을 구하면 된다. 그럼 정답은 $몫 \times 100 + D[나머지]$ 가 된다.

코드

#include <bits/stdc++.h>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlll;
#define xx first
#define yy second


int main(){
    fast_io
    string s; cin >> s;
    if(s[s.length()-1] == '5' || s[s.length()-1] == '0'){
        ll N = stoll(s.substr(0, s.length()-2));
        ll res = 0;
        if(s[s.length()-1] == '5'){
            N -= 4;
            res += 1;
        }

        ll Y = 900;
        ll a = N / Y;
        ll b = N % Y;
        vector<int> D(Y * 2 +1, -1);
        D[Y] = 0;
        queue<int> q; q.push(Y);
        while(!q.empty()){
            int now = q.front();
            q.pop();

            if(now + 9 <= 2 * Y && D[now + 9] == -1){
                D[now + 9] = D[now] + 1;
                q.push(now + 9);
            }
            if(now + 7 <= 2 * Y && D[now + 7] == -1){
                D[now + 7] = D[now] + 1;
                q.push(now + 7);
            }
            if(now - 2 >= 0 && D[now - 2] == -1){
                D[now-2] = D[now] + 1;
                q.push(now - 2);
            }
        }
        res += a * 100 + D[b + Y];
        cout << res << '\n';
    }else{
        cout << -1;
    }
}

35286 지하철! 지하철! 몇호선? 몇호선?

풀이

게임이론이고 더이상 지하철을 부를 수 없을 때 패배한다.

1, 3이면 확실히 선공이 이긴다. 2, 4면 확실히 후공이 이긴다. 4의 경우를 생각해보면 선공이 부른 값의 +2나 -2를 해서 모든 칸을 다 불러서 끝낼 수 있기 때문이다.

5의 경우도 후공이 뭘하던 선공은 모든 칸을 다 부를 수 있게 할 수 있다. 따라서 선공이 이긴다.

느낌상 홀수면 선공 승리, 짝수면 후공 승리의 느낌은 온다.

짝수를 생각해봤을 때, 후공이 스스로 고립되는 수를 부르지만 않으면 이긴다. 홀수는 선공이 짝수처럼 맨 끝을 불러서 시작할 수 있으니깐 상황이 역전된다.

꽤 생각하기 어렵지만 찍기도 쉽다.

코드

for _ in range(int(input())) : 
    N = int(input())
    print("H" if N & 1 else "S")