Jekyll2026-11-06T09:28:39+00:00https://whatsy12.github.io/rss/Seunggialt가 PS하는 블로그Seunggialt의 알고리즘 튜토리얼Seunggialt2026 전국 중학생 IT 올림피아드 후기 [디미고 대회]2026-11-05T18:32:17+00:002026-11-05T18:32:17+00:00https://whatsy12.github.io/dimigo/2026/11/05/dimigocontest2026예선

정올에서 1교시를 많이 못보는 편이기에 긴장했지만 생각보다 문제의 난이도가 쉬웠다. 문제가 너무 쉬워서 본선 예상컷이 만점이나 하나 틀린 정도로 예측했지만, 나도 본선에 붙어서 좀 놀랐다.

예선의 문제 비율은 조합론 80에 정수론 20 정도다. 공부 방법으로는 KMO 조합론, 정수론 책 사서 적당하게 풀면 될듯하다. 참고로 본인은 KMO에 나가지는 않아서 학교 쉬는시간이랑 점심시간 짬날때 조금씩 풀었다.

(예선은 준비안해도 통과하기 은근히 쉬운듯)

본선

3시간동안 5문제 정도를 풀어야 한다. 특별한 점이라면 코드를 제출해도 AC 현황을 알 수 없다. 난이도는 솔브드 기준 B S G G P 정도였던 것 같다.

시간이 은근히 촉박하기에 평소에 실버 ~ 골드 수준의 문제를 빨리 푸는 연습을 하는 것이 수상하는데 가장 효과적일 것 같다. 본인은 2번문제에서 시간을 많이 썼는데 문제가 어렵기보다는 구현실수를 하기 좋게 문제를 만드는 것 같다.

본인후기

느낌상 예선이랑 본선 둘다 정올보다는 쉽다.

딱히 수상할 것을 바라지 않았는데 내가 금상이여서 의외다. 예상보다 난이도는 쉬운데 시간이 부족했던 것이 아쉽고, 중2여서 다음년도 출전금지 당해서 아쉽다. 여담으로 2등 경품으로 게이밍 마우스를 받았는데 나는 게임을 딱히 안해서 현재 박스째 소장하는 중이다.

]]>
Seunggialt
여름학교 처음가서 문제풀때 느낀점(?)2026-11-05T17:32:17+00:002026-11-05T17:32:17+00:00https://whatsy12.github.io/else/2026/11/05/2026summer
  • 모든 경우 고려 / 특정 경우만 고려 = DP 같은 최적화 / 이탐 / 수학이나 그리디 기법
  • 비슷한 작업을 반복 / 한번만 하고 끝남 = 전처리 작업 & 이전에 했던거 활용 / 그때의 효율성 추구
  • 연산의 과정으로 답 구하기 / 답을 연산에 대입하기 = 평범한 최적화 유형 / 이분탐색같은 유형
  • 요소들끼리 관계 / 요소들끼리 관계 x = 그래프로 변환이 가능 / 그래프로 변환 불가
  • 지금까지는 이정도?

    특히 OI 어려운 문제는 답인것 같아도 다른 방법 시도 ⇒ 증명 어려우면 그냥 구현(새로운 접근별 구현 다른파일에 파기)

    풀이 알것같은데 구현 개빡세면 pass.

    풀이 알것같은데 뇌절 구현할것 같으면 일단 해.

    대신 간단하게 처음에 풀고 이후에 뇌절 풀이로 반드시 돌아가.

    가능하면 귀류법으로 반례 찾고 풀이 증명 간단하게.

    ]]>
    Seunggialt
    고양이 운동 문제풀이 [C++]2026-11-05T14:32:17+00:002026-11-05T14:32:17+00:00https://whatsy12.github.io/joi/2026/11/05/catexercisehttps://jungol.co.kr/problem/5834

    장애물이 설치되어 있는 노드를 기점으로 트리를 서브트리로 분활한다면 항상 고양이가 있는 노드가 포함되어 있는 서브트리에서 최대의 높이를 가진 정점은 고양이가 현재 있는 노드다. 최소 높이부터 유파로 서브트리의 크기를 늘리는 방법으로 접근하자. 두 서브트리를 합칠 때, 각 서브트리에 포함되는 최대 높이의 정점들 사이의 거리를 스파스 테이블로 효율적으로 구한다면 AC를 받을 수 있다.

    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define pii pair<ll, ll>
    #define x first
    #define y second
    
    ll n;
    vector<pii> v;
    vector<ll> d;
    vector<vector<ll>> arr;
    vector<ll> par;
    vector<ll> cache;
    vector<ll> depth;
    vector<vector<ll>> sparse;
    vector<vector<ll>> dist;
    ll SZ;
    
    ll Find(ll cur) {
        if (cur == par[cur]) return cur;
        return par[cur] = Find(par[cur]);
    }
    
    bool Union(ll a, ll b) {
        a = Find(a);
        b = Find(b);
        if (a == b) return false;
        par[a] = b;
        return true;
    }
    
    void Sparse() {
        for (ll i = 1; i <= SZ; i++) {
            for (ll j = 0; j < n; j++) {
                sparse[j][i] = sparse[sparse[j][i - 1]][i - 1];
                dist[j][i] = dist[j][i - 1] + dist[sparse[j][i - 1]][i - 1];
            }
        }
    }
    
    ll Dst(ll a, ll b) {
        if (depth[a] > depth[b]) swap(a, b);
        ll cost = 0;
        for (ll i = SZ; i >= 0; i--) {
            if (depth[sparse[b][i]] >= depth[a]) {
                cost += dist[b][i];
                b = sparse[b][i];
            }
        }
        if (a == b) return cost;
        for (ll i = SZ; i >= 0; i--) {
            if (sparse[a][i] != sparse[b][i]) {
                cost += dist[a][i];
                cost += dist[b][i];
                a = sparse[a][i];
                b = sparse[b][i];
            }
        }
        cost += 2;
        return cost;
    }
    
    int main(void) {
        cin >> n;
        for (SZ = 1; (1 << SZ) < n; SZ++);
        sparse.resize(n, vector<ll> (SZ + 1));
        dist.resize(n, vector<ll> (SZ + 1));
        v.resize(n);
        d.resize(n);
        arr.resize(n);
        par.resize(n);
        cache.resize(n, 0);
        iota(par.begin(), par.end(), 0);
        for (ll i = 0; i < n; i++) {
            cin >> v[i].x;
            v[i].y = i;
            d[i] = v[i].x;
        }
        sort(v.begin(), v.end());
        for (ll i = 0; i < n - 1; i++) {
            ll a, b;
            cin >> a >> b;
            a--;
            b--;
            arr[a].emplace_back(b);
            arr[b].emplace_back(a);
        }
        depth.resize(n);
        queue<ll> q;
        queue<ll> dpth;
        vector<bool> visited(n);
        q.emplace(0);
        dpth.emplace(0);
        sparse[0][0] = 0;
        dist[0][0] = 0;
        while (!q.empty()) {
            ll cur = q.front();
            q.pop();
            depth[cur] = dpth.front();
            dpth.pop();
            visited[cur] = true;
            for (auto i : arr[cur]) {
                if (visited[i]) continue;
                sparse[i][0] = cur;
                dist[i][0] = 1;
                visited[i] = true;
                q.emplace(i);
                dpth.emplace(depth[cur] + 1);
            }
        }
        Sparse();
        for (ll i = 0; i < n; i++) {
            ll cur = v[i].y;
            for (auto j : arr[cur]) {
                if (d[j] < d[cur]) {
                    ll idx = Find(j);
                    cache[cur] = max(cache[cur], cache[idx] + Dst(idx, cur));
                    Union(idx, cur);
                }
            }
            if (i == n - 1) cout << cache[cur];
        }
    }
    
    ]]>
    Seunggialt
    Make Money 돈 무한복사 튜토리얼2026-11-05T12:32:17+00:002026-11-05T12:32:17+00:00https://whatsy12.github.io/else/2026/11/05/makemoney학교에서 Make Money라는 크롬 확장 게임이 유행해서 이 글을 작성했다.

    돈 복사하는 법

    스크린샷 2026-11-06 오전 12 14 32 기본적으로 크롬 확장 프로그램에서 “개발자 도구”에 들어가야 한다.

    열려 있는 확장 프로그램의 탭을 크롬북의 경우에는 화면을 꾹 누르거나, 우클릭을 하면 아래와 같은 화면이 뜬다.

    image

    여기서 “검사” 버튼을 누르면 개발자 도구 화면에 들어간다.

    아래와 같은 화면이 나타나면 정상이다.

    image

    위와 같은 화면에서 우측 상단에 있는 “Console” 버튼을 누른다. (한국어로 번역이 되어있으면 “콘솔”과 같이 번역되어 있을 수 있음)

    image

    위 화면에서 “UPDATED CHECK: throttled” 아래에 있는 ‘>’ 에 코드를 작성할 수 있다.

    원래 상태에서는 코드를 복사하거나 붙여넣을 수 없기에, ‘>’ 우측에 아무 글자를 복사해서 입력한다.

    image

    지금까지 성공적으로 진행했다면 해당 화면이 나타날 것이다.

    영문으로 “allow pasting”을 입력하고, 아래 3개의 코드 중 아무 코드를 있는 그대로 붙여넣는다.

    • 돈, 보너스 클릭, 프레스티지 수정
    chrome.storage.sync.get("game_data", (data) => {
        let g = data.game_data;
        g.balance = 100000000000;
        g.bonus_clicks = 100000000;
        g.prestige_points = 1000;
        chrome.storage.sync.set({ game_data: g }, () => {
            console.log("Accepted");
            location.reload();
        });
    });
    
    • 모든 아이템 보유 처리
    chrome.storage.sync.get("game_data", (data) => {
        let g = data.game_data;
        for (let i = 1; i <= 23; i++) {
            g.items[i] = true;
        }
        chrome.storage.sync.set({ game_data: g }, () => {
            console.log("Accepted");
            location.reload();
        });
    });
    
    • 업그레이드 전부 구매 처리
    chrome.storage.sync.get("game_data", (data) => {
        let g = data.game_data;
        for (let i = 1; i <= 25; i++) {
            g.upgrade_details.income_boost.bought[i] = true;
        }
        for (let i = 1; i <= 50; i++) {
            g.upgrade_details.bonus_clicks.bought[i] = true;
        }
        chrome.storage.sync.set({ game_data: g }, () => {
            console.log("Accepted");
            location.reload();
        });
    });
    
    

    Troubleshooting

    게임이 멈췄거나 작동되지 않음

    • 사용자가 코드를 마음대로 바꾸어서 발생한 일이기에 우클릭 -> 검사 -> 콘솔 -> 코드를 그대로 붙여넣기 의 과정을 따르면 해결됨

    이외의 문제

    • 디스코드 seunggialt에 연락 부탁
    ]]>
    Seunggialt
    코딩을 처음 접하는 사람을 위해2025-11-03T13:01:36+00:002025-11-03T13:01:36+00:00https://whatsy12.github.io/tutorial/2025/11/03/codingpick코딩을 공부하고 싶은데 어디서 시작해야 하는지 모르겠다고요?

    차근차근 알려드립니다!

    무엇이 목표인가

    목표에 따라 배우는 방식이나 배우는 속도 등이 다를 수 있습니다

    예를 들어 게임 개발을 위해 배우는 사람은 게임과 관련되게 배우는 것이 좋겠지요?

    크게 3가지 부류로 나누겠습니다

    1. 학교 시험을 위해 공부하는 사람
    2. 프로젝트를 목표로 하는 사람
    3. 대회에 참석하거나 코딩 문제를 풀려 하는 사람

    세가지 배우는 목표에 따라 공부 방법이 매우 다릅니다.

    만약 이 셋에 모두 포함되지 않는다면 자신은 3번이라고 생각하시면 됩니다.

    학교 시험을 위해 공부하는 사람

    학교 시험에서의 코딩은 암기입니다.

    문제를 많이 푸는것도 중요하지만 시험범위에 해당에 해당하는 개념들을 완전히 숙지해야 합니다.

    다른거는 생각하지 마세요. 학교에서 나온 자료를 잘 활용하는 것이 중요합니다. 또, 기출문제를 푸는것도 매우 중요합니다. 학교에서 자주 내는 미끼 문제에 걸리지 않으려면 기출을 푸는 요령이 필요하니까요.

    프로젝트를 목표로 하는 사람

    주로 게임을 개발하거나 웹사이트를 만드는 목적을 지니는 사람들인데요, 아래는 목적에 따른 주요 사용 언어입니다.

    컴퓨터 프로그램: C++, C#, Java, Python

    웹사이트: PHP, Javascript, Python

    IOS 앱: Swift

    안드로이드 앱: Kotlin, Java, C++

    기본적으로 처음 시작할때부터 어려운 언어를 하면 조금 부담스러울 수 있기 때문에 코딩을 처음 배우는 단계로써 일단 Python을 추천합니다. 만약 조금 빨리 프로젝트를 하고 싶다는 마음이 있다면 목적에 맞는 언어를 선택해 주세요.

    배울 언어는 선택했고, 그렇다면 어떻게 공부해야 하는지 알아봅시다.

    ‘Mimo’라는 앱을 다운받아서 자신이 배우고자 하는 언어의 코스가 있는지 확인합니다. 만약 없다면, ‘Sololearn’이라는 앱을 다운받아 배우고자 하는 코스를 선택해서 배우면 됩니다!

    대회에 참석하거나 코딩 문제를 풀려 하는 사람

    코딩 문제를 푸는데 가장 많이 사용되는 언어는 C++, Python입니다. 자세한 설명은 아래 있습니다.

    Python:

    • 배우기 쉬움
    • 생산성이 좋음
    • 고난이도 문제를 해결하지 못하는 경우가 있음

    C++:

    • 상대적으로 배우기 어려움
    • 생산성이 상대적으로 떨어짐
    • 모든 문제를 해결할 수 있음

    저는 C++을 더 선호하기는 합니다.

    파이썬을 먼저 배우고 C++을 나중에 배우는 옵션도 있으니, 참고해주세요!

    ‘Mimo’라는 앱을 다운받아서 자신이 배우고자 하는 언어의 코스가 있는지 확인합니다. 만약 없다면, ‘Sololearn’이라는 앱을 다운받아 배우고자 하는 코스를 선택해서 배우면 됩니다!

    이제 문제를 푸는 연습을 할 것입니다! ‘백준’이라는 사이트에 들어가서 ’단계별로 풀어보기’에서 문제들을 차근차근 풀어봅니다! 모르는 문제를 인터넷에 검색하는 것을 두려워하지 마세요! 하지만 인터넷에 있는 코드를 그대로 배끼는 행위는 하면 안됩니다!

    ]]>
    Seunggialt
    2025 NYPC 1214 부문 본선 후기2025-10-25T23:32:17+00:002025-10-25T23:32:17+00:00https://whatsy12.github.io/nypc/2025/10/25/nypc2025시작 전

    SCC와 CCW를 간단하게 집에서 복습한 후, NYPC 대회장에 향했습니다.

    사실 본선진출은 한 것도 기적이여서 딱히 바라는 건 없었고, ‘그냥 키보드나 받자’라는 마음가짐으로 대회장에 도착했습니다.

    대회 시작

    1번 문제 (2분 소요)

    큰 어려움 없이 쉽게 해결하였습니다. 딱히 어려움 없이 쉽게 풀었습니다.

    2번 문제 (120분 소요)

    문제를 보자마자 국어로 가득하고, 왠지 구현일 것 같다는 느낌이 들어서 바로 문제만 읽고 스킵했습니다.

    나중에 돌아와서 유파로 문제를 풀었는데 계속해서 부분점수만 나왔습니다.

    사실 알고보니 버그 2개 때문에 문제가 발생하는 것이었습니다. 대회 종료 12분 전 정도에 버그를 발견하고 100점을 받았습니다.

    3번 문제(90분 소요)

    약간 게임이론 스타일의 문제여서 그리디 아니면 그런디를 활용해야 한다고 생각했습니다.

    햐지만 그런디를 활용하기에는 시간제한과 범위가 너무 빡쎄다고 판단하여 바로 그리디로 무리하게 도전하였습니다.

    예를 들어 홀수 짝수를 이용하여 문제를 해결하려 하였지만 사실상 불가능하다고 판단하여 섭태를 53점까지만 긁으려는 전략을 짰습나다.

    이전에 구해놓은 값들을 바탕으로 한번만 계산하면 되기 때문에 시간복잡도가 회기적으로 줄어들 수 있었습니다. 결과적으로 O(n ^ 3)의 풀이를 하며 53점을 획득하였습니다.

    4번 문제

    모르겠습니다.

    4번문제는 섭태를 긁기도 난이도가 어려운 듯하여 바로 포기했습니다.

    5번 문제 (10분 소요)

    문제를 잘못 이해하여 뻘짓을 하다가 제가 이해한 문제보다 훨씬 어려운 문제임을 깨닫게 되고 바로 포기했습니다.

    3점만 섭태로 따고 마무리하였습니다.

    수상

    놀랍게도 은상을 수상하였습니다.

    시상식에서 저처럼 너풀너풀 다니는 사람이 없는 것이 살짝 의외였지만 다 내향인인 것 같았습니다.

    사진을 다다스님과 함께 찍었는데, 그때 당시에는 제가 다다스님인줄 모르는 상태여서 나중에 알게 되었습니다.

    상품도 아주 푸짐하여 좋네요.

    EF13BA7E-1CF3-40FA-A766-B5B37595DF12_1_105_c

    소감

    2번 문제에서 심각하게 말려서 더 높은 상을 수상하지 못한 것이 아쉽긴 하나, 만족하는 ‘은상’이라는 결과를 얻어 기쁩니다.

    만약 2번 문제에서 뻘짓하지 않았더라면 5번 문제에서 섭태를 28에서 50점까지도 긁지 않았을까 싶습니다.

    아무튼 기분이 매우 좋고, 평소에 블로그에 글을 잘 올리지 않음에도 불구하고 너무나도 만족하는 결과를 얻어 자랑(?)하는 느낌으로 올리게 되었습니다.

    지금까지 seunggialt였습니다. 감사합니다!

    ]]>
    Seunggialt
    BOJ 3015 오아시스 재결합 해설2025-10-17T19:46:10+00:002025-10-17T19:46:10+00:00https://whatsy12.github.io/boj/2025/10/17/boj3015문제 링크

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

    해설

    개인적으로 이 문제를 해결하는 과정에서 어려움을 겪었습니다.

    아무리 생각해도 문제를 해결하기 위한 감도 잡히지 않아 인터넷 해설을 참고하여 해결한 문제입니다.

    알고리즘 분류

    그리디 스타일의 스택 활용 문제로, 스택을 활용하여 최적화를 해야 합니다.

    문제 해결

    만약 A라는 사람의 키가 B라는 앞 사람의 키보다 크다면, A뒤에 있는 사람들은 B를 볼 수 없게 됩니다.

    다른 말로, A 사람이 마지막으로 B 사람을 볼 수 있는 것입니다.

    이 특성을 활용하여, 앞 사람의 키가 현재 탐색하고 있는 사람의 키보다 작다면 앞 사람을 지울 수 있습니다.

    또, 만약 A와 B가 서로를 볼 수 있다면, A와 키가 같은 모든 사람을 볼 수 있습니다.

    이를 활용하여 연속되어 있는 같은 키의 갯수를 새주어, 효과적으로 표현하는 것입니다.

    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long int
    
    int main(void) {
        ll n;
        cin >> n;
        ll ans = 0;
        stack<pair<ll, ll>> s;
        while (n--) {
            ll x, cnt = 1;
            cin >> x;
            while (!s.empty() && x >= s.top().first) {
                ans += s.top().second;
                if (s.top().first == x) cnt = s.top().second + 1;
                s.pop();
            }
            if (!s.empty()) ans++;
            s.push({x, cnt});
        }
    }
    
    ]]>
    Seunggialt
    BOJ 2618 경찰차 해설2025-10-08T13:10:36+00:002025-10-08T13:10:36+00:00https://whatsy12.github.io/boj/2025/10/08/boj2618문제 링크

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

    해설

    알고리즘 분류

    DP와 역추적을 이용하는 문제로, 두 경찰차의 위치와 그 비용을 저장하는 방식의 DP를 사용할 수 있습니다.

    점화식 유도

    역추적 문제라는 것이 훤하게 드러나기 때문에 2차원 배열로 DP를 구성하는 것이 가장 적절하다고 판단하였습니다.
    두 경찰차가 사건으로 이동하는 경우의 수가 2의 거듭제곱 만큼 증가할 것이라 예상하고 완전이진 트리의 모습을 그릴 것이라 예상하였지만, 사실 도달하는 위치가 같은 좌표에서는 비용이 적은 곳을 선택하면 되기 때문에 파스칼의 삼각형(?)의 모양처럼 뻗어나가는 모습을 볼 수 있었습니다.
    물론 파스칼의 삼각형과 아무런 연관이 없음으로, 그냥 2차원 배열에 데이터를 집어넣는다는 생각으로 공식을 유도했습니다.
    설명한 바를 공식으로 유도하면 아래와 같습니다.

    $f(x, y) = max(f(x - 1, y) + \alpha, f(x, y - 1) + \beta)$
    참고로 $\alpha$와 $\beta$는 각각의 경찰차와 사건 장소 사이의 거리입니다.

    뭔가 그럴싸해 보이는 점화식이지만, 아직 수정해야 할 부분이 있습니다.
    바로 사건이 두 인덱스 $x$와 $y$에서 겹친다는 것입니다.
    예를 들어 1번 사건이 $x$에서 한번 진행되고, 나중에 $y - 1$에서 한번 진행하는 등, 중복을 배제해야 합니다.
    그렇기 때문에 실제로는 $x$ 값이 갱신할 때, $x + 1$로 갱신하는 것이 아닌, $max(x, y) + 1$로 갱신해야 하며, $y$도 마찬가지입니다.

    보통 역추적 문제에서는 $x - 1$이랑 $y - 1$을 비교하는 것이 가장 일반적이지만, $x$ 값과 $y$ 값이 어떻게 갱신될지 모르기 때문에 부모 정보를 따로 저장해야 합니다.

    소스코드

    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long int
    
    typedef struct police {
        ll x1, x2, y1, y2;
        ll ans = LLONG_MAX;
        ll bef;
        pair<ll, ll> par;
    }police;
    
    int main(void) {
        ios::sync_with_stdio(0);
        ll n;
        cin >> n;
        ll w;
        cin >> w;
        vector<ll> a(w + 1);
        vector<ll> b(w + 1);
        for (ll i = 1; i <= w; i++) {
            cin >> a[i] >> b[i];
        }
        vector<vector<police>> cache(w + 1, vector<police>(w + 1));
        police tmp;
        tmp.x1 = 1; tmp.y1 = 1; tmp.x2 = n; tmp.y2 = n; tmp.ans = 0;
        cache[0][0] = tmp;
        ll _max = LLONG_MAX;
        ll x, y;
        for (ll i = 0; i <= w; i++) {
            for (ll j = 0; j <= w; j++) {
                ll k = max(i, j) + 1;
                if (k > w || cache[i][j].ans == LLONG_MAX) continue;
                ll cost = abs(a[k] - cache[i][j].x1);
                cost += abs(b[k] - cache[i][j].y1);
                cost += cache[i][j].ans;
                if (cache[k][j].ans > cost) {
                    cache[k][j].bef = 1;
                    cache[k][j].ans = cost;
                    cache[k][j].x1 = a[k];
                    cache[k][j].y1 = b[k];
                    cache[k][j].x2 = cache[i][j].x2;
                    cache[k][j].y2 = cache[i][j].y2;
                    cache[k][j].par = {i, j};
                }
                if (k == w && _max > cache[k][j].ans) {
                    _max = cache[k][j].ans;
                    x = k;
                    y = j;
                }
                cost = abs(a[k] - cache[i][j].x2);
                cost += abs(b[k] - cache[i][j].y2);
                cost += cache[i][j].ans;
                if (cache[i][k].ans > cost) {
                    cache[i][k].bef = 2;
                    cache[i][k].ans = cost;
                    cache[i][k].x1 = cache[i][j].x1;
                    cache[i][k].y1 = cache[i][j].y1;
                    cache[i][k].x2 = a[k];
                    cache[i][k].y2 = b[k];
                    cache[i][k].par = {i, j};
                }
                if (k == w && _max > cache[i][k].ans) {
                    _max = cache[i][k].ans;
                    x = i;
                    y = k;
                }
            }
        }
        cout << _max << "\n";
        vector<ll> res(w);
        for (ll i = w - 1; i >= 0; i--) {
            res[i] = cache[x][y].bef;
            ll alp = x;
            ll beta = y;
            x = cache[alp][beta].par.first;
            y = cache[alp][beta].par.second;
        }
        for (ll i = 0; i < w; i++) {
            cout << res[i] << "\n";
        }
    }
    
    ]]>
    Seunggialt
    BOJ 17420 깊콘이 넘쳐흘러 해설2025-10-08T13:01:36+00:002025-10-08T13:01:36+00:00https://whatsy12.github.io/boj/2025/10/08/boj17420문제 링크

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

    해설

    시간복잡도

    $N$의 범위가 작기 때문에 $O(N)$의 시간복잡도로 문제를 풀 것이다.

    문제 풀이

    정우는 기한이 가장 적게 남은 기프티콘만을 사용할 수 있다.

    다른 말로, $B_i$가 가장 작을 때의 $i$는 $A_i$도 가장 작다.
    또, $B_i$가 가장 큰 값일 때의 $i$는 $B_i$도 가장 크다.
    이러한 성질 때문에, $B$를 오름차순 정렬했을때 대응되는 위치의 $A_i$ 값도 오름차순 정렬이 되어 있어야 한다.

    하지만, $A_i$의 크기가 $B_i$의 크기보다 커야 정우가 원하는 일자에 기프티콘을 사용할 수 있기 때문에 $A_i$ ≥ $B_i$ 이 성립한다.

    최종적으로 정리하자면, $B$를 오름차순 정렬하고 각 위치에 대응하는 곳에 $A_i$ 값들을 배치하면 아래의 두 식이 성립한다.
    $A_i$ ≥ $B_i$
    $A_{i - 1}$ ≤ $A_i$

    반례

    만약 $B_{i - 1}$과 $B_i$ 값이 같다면 굳이 $A_{i - 1}$ ≤ $A_i$ 식이 성립할 필요가 없다.
    그렇기 때문에, $B_i$ 보다 작은 값을 가지고 있는 최댓값을 $B$에서 찾은 후, 두 $A$ 값들을 비교해주면 된다.

    소스코드

    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long int
    
    int main(void) {
        ios::sync_with_stdio(0);
        ll n;
        cin >> n;
        vector<pair<ll, ll>> arr(n);
        for (ll i = 0; i < n; i++) {
            cin >> arr[i].second;
        }
        for (ll i = 0; i < n; i++) {
            cin >> arr[i].first;
        }
        sort(arr.begin(), arr.end());
        ll bef = ((max((ll)0, arr[0].first - arr[0].second + 29)) / 30) * 30 + arr[0].second;
        ll cnt = (max((ll)0, arr[0].first - arr[0].second + 29)) / 30;
        ll cache = 0;
        for (ll i = 1; i < n; i++) {
            ll tmp = (max((ll)0, max(bef, arr[i].first) - arr[i].second + 29)) / 30;
            cnt += tmp;
            if (i != n - 1 && arr[i + 1].first == arr[i].first) {
                cache = max(cache, tmp * 30 + arr[i].second);
                continue;
            }
            bef = tmp * 30 + arr[i].second;
            bef = max(bef, cache);
        }
        cout << cnt;
    }
    
    ]]>
    Seunggialt
    학교 Java 시험 벼락치기 튜토리얼 (1)2025-08-11T13:01:36+00:002025-08-11T13:01:36+00:00https://whatsy12.github.io/tutorial/2025/08/11/JAVAtutorial1IntelliJ 다운로드 및 설치

    https://www.jetbrains.com/idea/download/?section=windows

    위 링크를 통해 IntelliJ Community Edition을 다운받는다. (페이지 아래로 스크롤하면 있다!) 인터넷에 검색하면 사용법이 많이 나와 있으니, 이 글에서는 사용법을 생략한다.

    기본 출력

    IntelliJ에서 새로운 Java 프로젝트를 만들고 샘플 코드 추가를 활성화한다. 자동으로 Main.java 파일이 생성될 것이다.

    이제부터 public static void main(String[] args)의 두 중괄호 { } 사이에 코드를 작성할 것이다. 현재 중괄호 안에 있는 코드를 지우고, 아래 코드를 입력한다.

    System.out.print("Hello, world");
    

    그 후, 상단에 있는 초록색 화살표 버튼을 눌러 코드를 실행한다.

    출력:

    Hello, world
    

    Java에서는 System.out.print()를 이용해 화면에 글자를 출력한다. 출력하고자 하는 내용을 소괄호 안에 넣으면 된다.

    print와 println의 차이

    • System.out.print() : 값을 출력하고 줄바꿈을 하지 않음
    • System.out.println() : 값을 출력하고 줄바꿈을 함

    예를 들어 보겠다.

    코드:

    public class Main {
        public static void main(String[] args) {
            System.out.println("Hello world!");
            System.out.print("Hello ");
            System.out.print("world!");
        }
    }
    

    출력:

    Hello world!
    Hello world!
    

    계산 결과 출력하기

    소괄호 안에서 사칙연산(+, -, *, /)을 하는 것도 가능하다.

    코드:

    public class Main {
        public static void main(String[] args) {
            System.out.print("1 + 1 = ");
            System.out.print(1 + 1);
        }
    }
    

    출력:

    1 + 1 = 2
    

    변수

    코딩을 하다 보면 정보를 저장해야 하는 경우가 있는데, 그런 정보들을 저장할 수 있는 공간을 변수라고 한다.

    변수를 사용하려면 먼저 변수를 선언해야 한다.

    변수 선언 방법

    변수타입 변수이름;
    

    변수의 개념 이해하기

    실생활에 비유하여 설명하겠다. 물건들을 상자에 저장한다고 생각해보자.

    • 큰 물건은 큰 상자에, 작은 물건은 작은 상자에 넣어야 한다
    • 깨지기 쉬운 물건은 완충제를 함께 넣어야 한다
    • 상자에 내용물 이름을 적은 스티커를 붙여야 나중에 찾을 수 있다

    Java의 변수도 마찬가지다:

    • 정보의 크기와 형태에 따라 적절한 변수타입이 필요하다
    • 무엇이 저장되어 있는지 알 수 있도록 변수이름을 붙여야 한다

    정수형 변수 사용 예시

    정수(integer)를 저장하는 변수는 int 타입을 사용한다.

    int 변수이름;
    

    변수에 값을 저장하거나 변경하려면:

    변수이름 = 저장할값;
    

    예시 코드:

    public class Main {
        public static void main(String[] args) {
            int x = 5;
            System.out.println(x);
            x = 3;
            System.out.print(x);
        }
    }
    

    출력:

    5
    3
    

    변수를 이용한 계산

    예시 코드:

    public class Main {
        public static void main(String[] args) {
            int x = 4;
            int y = 2;
            System.out.println(x + y);
            System.out.println(x - y);
            System.out.println(x * y);
            System.out.println(x / y);
        }
    }
    

    출력:

    6
    2
    8
    2
    

    변수 타입 기본 (중요!)

    가장 많이 사용되는 변수 타입들에 대해 알아보자.

    주요 변수 타입

    타입 설명 비고
    int, long 정수 저장 20억 초과 시 long 사용
    float, double 실수(소수) 저장 float은 7자리, double은 15자리 정밀도
    char 문자 하나 저장 작은따옴표 사용: ‘a’
    String 여러 문자(문자열) 저장 큰따옴표 사용: “hello”

    변수의 활용 (중요!)

    변수 타입에 따라 값에 접미사가 붙는 경우가 있다. 이것은 암기가 필수다!

    접미사 규칙

    타입 접미사 예시
    long L 또는 l 100L
    8진수 0 077
    16진수 0x 또는 0X 0xFF
    float f 또는 F 3.14f
    double d 또는 D 3.14d (생략 가능)

    참고: 큰 숫자는 가독성을 위해 중간에 _(언더스코어)를 넣을 수 있다.

    int million = 1_000_000;
    

    변수의 활용 - 간단한 예시

    각 타입별 실제 사용 예시:

    타입 예시 비고
    논리형 false, true 접미사 없음
    정수형 12, 100L L 접미사는 long
    실수형 3.14, 3.0f f는 float, 없으면 double
    문자형 'a', 'A' 작은따옴표, 문자 1개
    문자열 "AB", "hello" 큰따옴표, 여러 문자

    참고: 논리형(boolean)은 조건문에서 다루므로 지금은 참고만 하자.


    입력 받기

    지금까지는 정보를 출력하는 방법을 배웠다. 이제는 사용자로부터 정보를 입력받는 방법을 알아보겠다.

    Java에서 입력을 받으려면 Scanner라는 클래스를 사용해야 한다. 먼저 코드 맨 위에 다음과 같이 작성한다.

    import java.util.Scanner;
    

    그 다음, main 메소드 안에서 Scanner 객체를 생성한다.

    Scanner sc = new Scanner(System.in);
    

    입력 받기의 기본

    Scanner를 사용하면 다양한 타입의 데이터를 입력받을 수 있다.

    • sc.nextInt() : 정수 입력받기
    • sc.nextLong() : long 타입 정수 입력받기
    • sc.nextFloat() : float 타입 실수 입력받기
    • sc.nextDouble() : double 타입 실수 입력받기
    • sc.next() : 공백 전까지의 문자열 입력받기
    • sc.nextLine() : 한 줄 전체를 문자열로 입력받기

    예시 코드:

    import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            
            System.out.print("정수를 입력하세요: ");
            int num = sc.nextInt();
            System.out.println("입력한 정수: " + num);
            
            System.out.print("이름을 입력하세요: ");
            String name = sc.next();
            System.out.println("안녕하세요, " + name + "님!");
        }
    }
    

    출력 예시:

    정수를 입력하세요: 10
    입력한 정수: 10
    이름을 입력하세요: 홍길동
    안녕하세요, 홍길동님!
    

    주의사항

    nextLine()을 사용할 때는 주의가 필요하다. 다른 next 메소드들을 사용한 후에 nextLine()을 사용하면, 남아있는 개행문자(\n)를 읽어버려 빈 문자열이 입력될 수 있다.

    예시:

    Scanner sc = new Scanner(System.in);
    int num = sc.nextInt();
    sc.nextLine(); // 버퍼에 남은 개행문자 제거
    String str = sc.nextLine();
    

    조건문 (if문)

    프로그래밍을 하다 보면 특정 조건에 따라 다른 동작을 해야 하는 경우가 많다. 이럴 때 사용하는 것이 조건문이다.

    if문의 기본 구조

    if (조건) {
        // 조건이 참일 때 실행되는 코드
    }
    

    예시 코드:

    public class Main {
        public static void main(String[] args) {
            int score = 85;
            
            if (score >= 80) {
                System.out.println("합격입니다!");
            }
        }
    }
    

    출력:

    합격입니다!
    

    if-else문

    if (조건) {
        // 조건이 참일 때 실행
    } else {
        // 조건이 거짓일 때 실행
    }
    

    예시 코드:

    public class Main {
        public static void main(String[] args) {
            int age = 15;
            
            if (age >= 18) {
                System.out.println("성인입니다.");
            } else {
                System.out.println("미성년자입니다.");
            }
        }
    }
    

    출력:

    미성년자입니다.
    

    if-else if-else문

    여러 조건을 검사해야 할 때 사용한다.

    if (조건1) {
        // 조건1이 참일 때
    } else if (조건2) {
        // 조건2가 참일 때
    } else if (조건3) {
        // 조건3이 참일 때
    } else {
        // 모든 조건이 거짓일 때
    }
    

    예시 코드:

    public class Main {
        public static void main(String[] args) {
            int score = 85;
            
            if (score >= 90) {
                System.out.println("A학점");
            } else if (score >= 80) {
                System.out.println("B학점");
            } else if (score >= 70) {
                System.out.println("C학점");
            } else {
                System.out.println("F학점");
            }
        }
    }
    

    출력:

    B학점
    

    비교 연산자

    조건문에서 사용되는 주요 비교 연산자들:

    • == : 같다
    • != : 같지 않다
    • > : 크다
    • < : 작다
    • >= : 크거나 같다
    • <= : 작거나 같다

    논리 연산자

    여러 조건을 조합할 때 사용:

    • && : AND (그리고) - 모든 조건이 참이어야 함
    • || : OR (또는) - 하나라도 참이면 됨
    • ! : NOT (부정) - 참을 거짓으로, 거짓을 참으로

    예시 코드:

    public class Main {
        public static void main(String[] args) {
            int age = 20;
            boolean hasLicense = true;
            
            if (age >= 18 && hasLicense) {
                System.out.println("운전할 수 있습니다.");
            } else {
                System.out.println("운전할 수 없습니다.");
            }
        }
    }
    

    출력:

    운전할 수 있습니다.
    

    반복문

    같은 작업을 여러 번 반복해야 할 때 반복문을 사용한다.

    for문

    정해진 횟수만큼 반복할 때 주로 사용한다.

    for (초기식; 조건식; 증감식) {
        // 반복할 코드
    }
    

    예시 코드:

    public class Main {
        public static void main(String[] args) {
            for (int i = 1; i <= 5; i++) {
                System.out.println(i + "번째 반복");
            }
        }
    }
    

    출력:

    1번째 반복
    2번째 반복
    3번째 반복
    4번째 반복
    5번째 반복
    

    while문

    조건이 참인 동안 계속 반복한다.

    while (조건) {
        // 반복할 코드
    }
    

    예시 코드:

    public class Main {
        public static void main(String[] args) {
            int count = 1;
            
            while (count <= 5) {
                System.out.println("카운트: " + count);
                count++;
            }
        }
    }
    

    출력:

    카운트: 1
    카운트: 2
    카운트: 3
    카운트: 4
    카운트: 5
    

    do-while문

    최소 한 번은 실행하고, 그 후 조건을 검사한다.

    do {
        // 반복할 코드
    } while (조건);
    

    예시 코드:

    public class Main {
        public static void main(String[] args) {
            int num = 10;
            
            do {
                System.out.println("숫자: " + num);
                num--;
            } while (num > 5);
        }
    }
    

    출력:

    숫자: 10
    숫자: 9
    숫자: 8
    숫자: 7
    숫자: 6
    

    break와 continue

    • break : 반복문을 즉시 종료
    • continue : 현재 반복을 건너뛰고 다음 반복으로

    예시 코드:

    public class Main {
        public static void main(String[] args) {
            // break 예시
            for (int i = 1; i <= 10; i++) {
                if (i == 5) {
                    break;
                }
                System.out.println(i);
            }
            
            System.out.println("---");
            
            // continue 예시
            for (int i = 1; i <= 5; i++) {
                if (i == 3) {
                    continue;
                }
                System.out.println(i);
            }
        }
    }
    

    출력:

    1
    2
    3
    4
    ---
    1
    2
    4
    5
    

    다음 내용에서는 배열, 메소드, 클래스와 객체 등 더 심화된 내용을 다룰 예정이다.​​​​​​​​​​​​​​​​

    오류제보

    C++ 메인으로 코딩을 하다 보니, 실수를 하는 경우가 많다. 만약 오류 제보를 하고 싶다면 디스코드 아이디 _wha7y_를 통해 제보하시길 바란다.

    ]]>
    Seunggialt