[백준/BOJ] 1049번 : 기타줄, 9613번 : GCD 합, 21921번 : 블로그

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 1049번 : '기타줄', 9613번 : 'GCD 합', 21921번 : '블로그' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Silver 티어에 해당하며, 무작위로 문제를 뽑아 풀었기 때문에 카테고리는 랜덤입니다.

 

 

1049번 : 기타줄

 

기타 줄을 6개 묶음 또는 낱개로 살 수 있고, 가격이 다른 브랜드가 M가지가 있을 때 N개의 줄을 살 수 있는 최소 가격을 구하는 문제입니다.

 

이런 그리디 문제의 경우에는 경우를 세워서 어떤 경우 어떤 것이 싼지 체크해보는 것도 좋지만, 빨리 풀고 싶을 때는 그냥 나올 수 있는 경우의 수식들을 모두 세운 뒤 그 중 최솟값을 구하면 됩니다.

가령 이 문제에서는 다음의 3가지 경우 중 하나로 최솟값이 나옵니다.

 

( i ) 개수가 좀 남더라도 넉넉하게 묶음으로 전부 사버리는 경우

( ii ) 모두 낱개로 사는 경우

( iii ) 6개 단위가 들어갈 수 있는 수만큼은 묶음으로 사고, 나머지를 낱개로 사는 경우

 

위의 3가지 식을 비교하여 최솟값을 답으로 구하도록 구현해봅시다.

 

 

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

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

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

    int bunch[100], piece[100];
    for(int i=0; i<M; i++)
        cin >> bunch[i] >> piece[i];

    sort(bunch, bunch+M);
    sort(piece, piece+M);

    cout << min(((N-1)/6 + 1)*bunch[0], min(N*piece[0], N/6*bunch[0] + N%6*piece[0]));
}

 

1, 2, 3번 경우 순서대로 마지막 줄에 구현한 정답 코드입니다.

묶음으로 사는 경우 수식을 (N - 1)/6 + 1과 같이 구현한 이유는 N이 6의 배수인 경우 1개를 더 사야하는데 이 경계선을 명확히 구현하기 위해서 1을 빼서 정수 몫을 구하고 1을 더해주는 방식으로 구현한 것입니다.

 

나머지는 위의 설명과 똑같이 구현하였으니 참고하시면 됩니다.

 

 

 

 

 

9613번 : GCD 합

 

정수 N개 중에서 선택 가능한 두 정수의 GCD의 합을 구하는 문제입니다.

정수 두 개로 이루어진 모든 쌍을 구하는 것은 이중 for문으로 쉽게 가능하니, 핵심은 GCD를 짧은 시간에 구하는 '유클리드 호제법'을 사용하는 것입니다.

따라서 유클리드 호제법으로 gcd를 구해주는 부분만 구현하면 정답 처리를 받을 수 있습니다.

 

 

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

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

    int T; cin >> T;

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

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

        long long sum = 0;
        for(int i=0; i<N; i++)
            for(int j=i+1; j<N; j++) {
                int a = arr[i], b = arr[j];

                if(a < b) swap(a, b);

                while(b > 0) {
                    int temp = a % b;
                    a = b;
                    b = temp;
                }

                sum += (long long) a;
            }

        cout << sum << "\n";
    }
}

 

가장 간단하게 구하는 방법은 a > b인 상태에서, temp = a%b로 넘겨주고 a = b로, b = temp로 전환해주는 과정을 b가 0이 될 때까지 반복하는 것입니다.

 

그리고 이 문제에서 주의할 점은 sum이 int 범위를 넘어갈 수 있으므로 long long sum으로 선언해주는 것이 바람직합니다.

 

 

 

 

21921번 : 블로그

 

각 날짜동안의 블로그 방문자수가 입력으로 주어질 때, X일 동안 가장 많이 들어왔던 구간을 찾아서 그 방문자 수를 구하는 문제입니다.

 

간단한 "슬라이딩 윈도우" 알고리즘 문제입니다.

슬라이딩 윈도우 알고리즘이란 범위가 변화하는 구간의 구간합을 겹치는 부분은 그대로 두고 범위가 바뀌는 부분만 연산하여 연산 속도를 줄이는 알고리즘입니다.

 

아래에 간단히 풀이를 구현해보겠습니다.

 

 

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

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

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

    vector<int> arr(N);

    int sum = 0;
    for(int i=0; i<M; i++) {
        cin >> arr[i];
        sum += arr[i];
    }

    int Max = sum, MaxCnt = 1;
    for(int i=M; i<N; i++) {
        cin >> arr[i];
        sum = sum + arr[i] - arr[i-M];

        if(sum > Max) Max = sum, MaxCnt = 1;
        else if(sum == Max) MaxCnt++;
    }

    if(Max == 0) cout << "SAD";
    else cout << Max << "\n" << MaxCnt;
}

 

우선 위와 같이 M일에 해당하는 맨 앞의 구간 합을 먼저 구해줍니다.

그 다음 하루씩 뒤로 미루면서 새로운 구간합을 구할 것인데, 이 경우 맨 앞에 있는 날짜의 방문자 수를 빼주고 새로 추가되는 날짜의 방문자 수를 더해주기만 하면 새로운 구간합을 구할 수 있습니다.

이러한 연산의 반복을 구간이 맨 끝으로 도달할 때까지 반복해주면서 max 값을 갱신해주면 됩니다.