220710 PS 일기 : 구간 합 나머지 O(N)에 구하기, 실수 오차 잡는 법 (임의 정밀도) 등

알고리즘에 대한 글을 작성하면 일반적으로 하나의 주제를 잡고 정리해야 하는데, 글 하나에 정리할 정도로 내용이 많지 않은 작은 테크닉이나 단일 문제들의 경우 포스트 하나마다 따로 작성하기가 용이하지 않기 때문에, 이 카테고리에 큰 형식의 틀 없이 모아서 작성해보려고 한다.

 

 

백준 BOJ 10986번 : 나머지 합

N개의 수로 이루어진 수열에 대해 연속된 구간의 합이 M으로 나누어 떨어지는 구간의 수를 구하는 문제이다. (1 ≤ N ≤ 10^6)

가장 먼저 떠오르는 풀이는 누적 합을 이용해서 O(N^2)에 푸는 건데, 그렇게 할 경우 당연히 시간 초과이다.

 

i ~ j번째 구간의 합이 M으로 나눈 나머지가 0이라는 것과 동치는 무엇일까?

누적 합을 이용하여 생각해보면, 1 ~ j번째 구간 합에서 1 ~ (i-1)번째 구간 합을 뺀 값을 M으로 나눈 나머지가 0이면 된다.

즉, 1 ~ j번째 구간 합을 M으로 나눈 나머지와 1 ~ (i-1)번째 구간 합을 M으로 나눈 나머지가 같으면 된다.

 

따라서 1 ~ k번째 구간 합을 모두 구하여 (1 <= k <= N) M으로 나눈 나머지를 count 해주고, 각 count에 대해 x C 2를 구해서 합해주면 된다.

이 때 구간이라는 것은 길이가 1일수도 있기 때문에 단일 원소가 M으로 나누어 떨어지는 경우를 더해주면 된다. (윗 줄에서 구한 개수는 i < j인 경우를 센 것이므로 i = j인 경우를 count 해준다는 뜻)

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    vector<int> v(N+1);
    for(int i=1; i<=N; i++) {
        int x; cin >> x;
        v[i] = v[i-1] + x;
    }

    vector<int> u(M);
    for(int i=1; i<=N; i++) u[v[i] % M]++;

    int ans = 0;
    for(int i=1; i<=N; i++)
        if(v[i] % M == 0) ans++;
    for(int i=0; i<M; i++) ans += u[i] * (u[i] - 1) / 2;

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

 

 

쉬운 문제들 풀기

이후에는 머리 식힐 겸 부계정으로 쉬운 문제들을 다시 풀었다.

골드 이상의 문제들은 2회독 할 목적으로 다시 풀어보는 것도 좋은 방법인 것 같다.

solved.ac에서 검색 조건식을 !@$me로 검색하고 푼 사람 수 내림차순 정렬을 하여 풀거나 아무 문제나 골라서 푼다.

 

 

실수 오차 잡기 (임의 정밀도)

백준 BOJ 11262번 : Minion's Master 문제를 풀면서 실수 오차를 다루는 법을 다시 리마인드 할 수 있었다.

실수 오차를 이용하여 반올림시 값이 다르게 나오도록 준비한 극악의 데이터가 들어올 경우 실수 오차 때문에 답이 틀리게 나올 수 있다.

이를 보정하기 위해 최종 답에 1e-10 정도를 더해주면 정답 처리를 받을 수 있다.

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cout << fixed;
    cout.precision(3);

    int T; cin >> T;

    while(T--) {
        int N; cin >> N;

        vector<double> v(N);
        for(int i=0; i<N; i++) cin >> v[i];

        double sum = 0;
        for(int i=0; i<N; i++) sum += v[i];

        int cnt = 0;
        for(int i=0; i<N; i++)
            if(v[i] * N > sum) cnt++;

        cout << (sum / N) + 1e-10 << " ";
        cout << ((double)cnt / N * 100) + 1e-10 << "%\n";
    }
}

 

비슷한 컨셉의 풀어 보면 좋은 문제로는 백준 BOJ 2755번 : '이번학기 평점은 몇점?' 문제가 있다.

피자와 관련된 문제도 있었던 것 같은데 기억이 나면 수정하여 추가할 수 있도록 하겠다.

 

 

물리적으로 반사되는 경우 편하게 계산하는 트릭

백준 BOJ 4406번 : Biliard 문제를 풀면 참신한 방법으로 문제를 해결할 수 있다.

당구대에서 공이 몇 번 반사되었는지를 알려주고 경로의 길이나 공의 속력을 구하는 문제인데 하나의 당구대를 직사각형으로 보고 여러 번 뒤집어서 이어 붙여주면 경로를 직선으로 그릴 수 있게 된다.

 

 

 

카테고리가 공부 일기인만큼 그림은 대충 그려본다.

어려운 문제는 아니지만 옛날에 비슷한 방식으로 풀었던 물리 문제가 기억나서 적어보게 되었다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cout << fixed;
    cout.precision(2);

    while(true) {
        int a, b, s, m, n; cin >> a >> b >> s >> m >> n;
        if(a == 0 && b == 0 && s == 0 && m == 0 && n == 0) break;

        double x = a * (m + 1/2);
        double y = b * (n + 1/2);

        double ang = atan((double)y/x) * (180.0 / M_PI);
        double vel = sqrt(x*x + y*y) / s;

        cout << ang << " " << vel << "\n";
    }
}

 

풀이 코드는 위와 같다.