cyj893

저장소

백준: Gold5 - 2436, 2493, 2589

4 분 소요


계속

2436: 공약수

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

어떤 두 수의 최대공약수와 최소공배수를 입력 받았을 때, 그 두 수의 합이 최소가 되는 두 수 구하기

#include <bits/stdc++.h>

using namespace std;

vector<int> v;
int ansa, ansb;
int a, b;

void func(int ind, int before, int cnt){
    if( cnt == 0 ){
        if( a*before + b/before < ansa + ansb ){
            ansa = a*before;
            ansb = b/before;
        }
        return;
    }
    for(int i = ind+1; i < v.size(); i++){
        func(i, before*v[i], cnt-1);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> a >> b;

    int c = b/a;
    for(int i = 2; i <= c; i++){
        if( c % i == 0 ){
            int k = 1;
            while( c % i == 0 ){
                k *= i;
                c /= i;
            }
            v.push_back(k);
        }
    }

    ansa = a; ansb = b;
    for(int i = 0; i <= v.size()/2; i++){
        func(-1, 1, i);
    }

    cout << min(ansa, ansb) << ' ' << max(ansa, ansb) << endl;

}

최대공약수를 a, 최소공배수를 b라고 하면 찾아야 하는 두 수들은 b/a의 약수들을 나눠 가진다는 것을 알 수 있다. 예제인 6, 180을 보면

b/a = 180/6 = 30 = 2 * 3 * 5

a가 최대공약수, b가 최소공배수인 두 수들은
(a, a*2*3*5), (a*2, a*3*5), (a*3, a*2*5), (a*5, a*2*3)

두 수끼리 공약수가 또 있으면 안 되므로,
예를 들어 b/a = 2^n * 3^m * ...인 경우 2^n과 3^m 등으로 통째로 나눠야 함


2493: 탑

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

각 탑들이 왼쪽으로 빛을 쏠 때 가장 먼저 만나는 탑의 인덱스 구하기

방법 1.

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

int arr[500001];
int ans[500001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }

    priority_queue<P, vector<P>, greater<P>> pq;
    for(int i = n; i > 0; i--){
        while( pq.size() && pq.top().first <= arr[i] ){
            ans[pq.top().second] = i;
            pq.pop();
        }
        pq.push(make_pair(arr[i], i));
    }

    for(int i = 1; i <= n; i++){
        cout << ans[i] << ' ';
    }

}

일단 떠오른 대로 무지성 풀이는 뒤에서부터, (탑 높이, 인덱스)를 우선순위 큐에 넣고, 자기보다 같거나 큰 탑이 나올 때마다 팝하면서 인덱스를 저장해주면 될 것 같다
N은 최대 50만인데, 우선순위 큐는 시간 복잡도가 O(logN)이고, 포문 한 번 도니까 총 O(NlogN)일 듯

방법 2.

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

int arr[500001];
int ans[500001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }

    stack<P> st;
    for(int i = 1; i <= n; i++){
        while( st.size() && st.top().first < arr[i] ){
            st.pop();
        }
        ans[i] = st.size() ? st.top().second : 0;
        st.push(make_pair(arr[i], i));
    }

    for(int i = 1; i <= n; i++){
        cout << ans[i] << ' ';
    }

}

하지만 보통 이런 문제는 스택으로 풀겠지 싶어서 다시 생각해 봄
이번엔 앞에서부터, 얘가 나랑 만나는 지를 확인하면 된다
만약 스택의 탑이 나보다 작으면 안 만나는 애고, 나보다 뒤의 탑들도 얘를 만날 일이 없으니 팝한다
다 끝나고, 스택이 남아 있으면 스택의 탑이 내가 만나는 애니까 걔로 답을 하고, 없으면 만나는 애가 없으므로 0이다.
그 후 나도 스택에 들어가면 끝

2589: 보물섬

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

육지와 바다가 지도에 주어질 때, 육지의 가장 최단거리로 간다고 가정할 때 가장 오래 걸리는 거리 구하기

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

int mmap[51][51];
int visited[51][51];
int n, m;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int ans = 0;

void func(int nowx, int nowy){
    queue<P> q;
    q.push(make_pair(nowx, nowy));
    visited[nowx][nowy] = 0;
    while( q.size() ){
        int x = q.front().first;
        int y = q.front().second;
        int d = visited[x][y];
        q.pop();

        ans = max(ans, d);

        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if( nx < 0 || n <= nx
               || ny < 0 || m <= ny
               || visited[nx][ny] <= d+1 || mmap[nx][ny] == 0 ) continue;
            visited[nx][ny] = min(visited[nx][ny], d+1);
            q.push(make_pair(nx, ny));
        }
    }

    /*
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if( visited[i][j] == 2501 ) cout << "x" << ' ';
            else cout << visited[i][j] << ' ';
        }
        cout << "\n";
    }
    */
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        for(int j = 0; j < m; j++){
            mmap[i][j] = s[j] == 'W' ? 0 : 1;
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if( mmap[i][j] == 0 ) continue;
            for(int ii = 0; ii < n; ii++){
                for(int jj = 0; jj < m; jj++){
                    visited[ii][jj] = 2501;
                }
            }
            func(i, j);
            //cout << i << ' ' << j << ' ' << ans << "\n\n";
        }
    }

    cout << ans << endl;

}

간단한 bfs로 다 뒤지면 된다
다음 위치가 지도 범위 내에 있고, 혹시 더 적은 시간으로 이미 방문한 곳인지 확인하고, 육지인지 확인하고 큐에 넣어준다

ex) 백준 예제
x 4 5 x x x x
2 3 4 x x x x
1 x 5 x x x x
0 x 6 x x x x
x 8 7 x x x x
(3, 0)에서 출발, (4, 1)에 도착


굿

댓글남기기

참고