[Algorithm] 백준 알고리즘 기초 2/2 - 건너 뛰며 해보기

건너 뛰며 해보기

건너 뛰며 해보기는 모든 경우의 수를 다 안 해봐도 된다고 판단될 경우에 몇 가지를 생략하고 넘어가는 것을 말한다.

백준 6064번 - 카잉 달력

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

$M$과 $N$보다 작거나 같은 자연수 $x$, $y$를 가지고 각 년도를 < $x$ : $y$ >와 같은 형식으로 표현한다.

< $x$ : $y$ >의 다음 해를 < $x^{\prime}$ : $y^{\prime}$ >이라고 할 때, $x\lt{M}$이면 $x^{\prime}=x+1$이고, 그렇지 않으면 $x^{\prime}=1$이다. $y$의 경우도 마찬가지다.

네 개의 정수 $M$, $N(1\leq{M,N}\leq{40,000}), x(1\leq{x}\leq{M}), y(1\leq{y}\leq{N})$가 주어질 때,

< $1$ : $1$ >이 첫 번째 해이고, < $M$ : $N$ >이 카잉 달력의 마지막 해라고 하면 < $x$ : $y$ >는 몇 번째 해인지 구한다.

시간 제한: 1초

각 $M$에 대해 각 $N$을 해보면 되므로 브루트 포스 알고리즘의 시간 복잡도는 $O(MN)$이다.

하지만, $1\leq{M}, N\leq{40,000}$의 조건 때문에 브루트 포스 알고리즘으로 해결할 수 없다.

이를 해결하기 위해 해의 한 쪽을 $x$로 고정하거나, $y$로 고정하여 다른 한 쪽만 브루트 포싱한다.

예를 들어, $M=5$, $N=7$, $x=3$, $y=2$일 때

<1, 1>, <2, 2>, <3, 3>에서

<2, 2>는 뒷 자리가 $y$를 만족하고,

<3, 3>은 앞 자리가 $x$를 만족한다.

그리고 이 중 <3, 3>을 선택하여 $x$가 고정된 상태에서의 다음 해는 <3, 1>이다. 그 이유는 $M=5$이기 때문이다.

다시 말하면, $x$를 이용해 모든 해를 고려하지 않고, $i\times{M}+x(i\geq{0})$의 형태만 조사하면 된다.

소스코드(C++)

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    while(b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while(t--) {
        int m, n, x, y;
        cin >> m >> n >> x >> y;
        int cnt;
        int k = -1;
        int limit = lcm(m, n);
        for(int i = 0; x + i * m <= limit; i++) {
            cnt = x + i * m - n * ((x + i * m) / n);
            if(cnt == y || cnt == 0 && n == y) {
                k = x + i * m;
                break;
            }
        }
        cout << k << '\n';
    }

    return 0;
}

 

백준 1748번 - 수 이어 쓰기 1

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

1부터 $N(1\leq{N}\leq{100,000,000})$까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

$12345678910111213...$

이렇게 만들어진 새로운 수가 몇 자리 수인지 구한다.

시간 제한: 1초

경우의 수가 1억이고 방법 1개를 시도하는 데 걸리는 시간이 평균적으로 1을 훨씬 넘기 때문에 브루트 포스 알고리즘으로 해결할 수 없다.

이를 해결하기 위해 수를 자리수별로 나눈다.

예를 들어, $N=120$일 때

$1 - 9(한 자리수) = (9 - 1 + 1)\times{1}$

$10 - 99(두 자리수) = (99 - 10 + 1)\times{2}$

$100 - 120(세 자리수) = (120 - 100 + 1)\times{3}$

소스코드(C++)

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    long long ans = 0;
    for (int start = 1, len = 1; start <= n; start *= 10, len++) {
        int end = start * 10 - 1;
        if (end > n) {
            end = n;
        }
        ans += (long long)(end - start + 1) * len;
    }
    cout << ans << '\n';
    return 0;
}