22.06.02. 풀었던 문제들

한 10일 쉰 것 같다! 그동안 탁구 배우면서 잘 쉬었던 것 같다. 외박도 다녀왔고 이제부터 다시 열심히 공부해야겠다!

​

1. 경주로 건설

일단 graph 문제이고, 최소값을 리턴하기 때문에 -> dijkstra를 사용해야만 한다. 그리고 v[max_r][max_c]를사용하는 것이 아니라, v[max_r][max_c][max_dire] 이렇게 3차원 배열로 풀어야만 하는 문제였다. 이렇게 해야 하는 이유는 반례가 있기 때문이다.

생각해 보자. (n, n) 좌표가 도착지점이다. 그리고 (n, n-1)지점이 (n, n)으로 갈 때 최솟값 경로에 속해있는 값이라 치자. 이 때, (n, n-2) 지점에서 오는 것과 (n-1, n-1)지점에서 올 때는 값이 달라질 수 있다. 아래 예제와 같이 (n-1, n-2) - (n-1, n-1) - (n, n-1)로 가면 (n, n-1)지점의 값이 3600이다. 그리고 (n, n-1)지점에서 (n, n) 지점으로 갈 때는 코너가 하나 더 생기기 때문에 4100이 된다 - 이 경우를 A경우라 두자.

그러나 (n, n-3) - (n, n-2) - (n, n-1)으로 가면 (n, n-1) 지점의 값은 3700이고, (n, n) 지점의 값은 3800이다. 이 경우를 B경우라 두자.

			n-1	n
n-1		2900 ->	3000 |
n	3500 ->	3600 ->	위에서 내려오면 3600 왼쪽에서 오면 3700	도착지점 답은 3800

B경우가 optimal함에도 불구하고 2차원 배열로 각 element에 최소 cost만 저장해 버리면 위와 같은 반례가 생긴다. 따라서 '이전에 어떤 경로로 왔는지'에 대한 데이터가 필요하며 - 따라서 3차원 배열로 작성해야만 한다. 이 반례때문에 상-당히 골때렸다.

 

// 경주로 건설

#include <string>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> pii;
struct rd{
    int row;
    int col;
    int dir;
};

int MAX = 2100000000, answer = MAX;
int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};
// 0 : down, 1 : right, 2 : up, 3 : left

int solution(vector<vector<int>> board) {
    int n = board.size();
    vector<vector<vector<int>>> road(n, vector<vector<int>>(n, vector<int>(4, MAX)));
    for(int i = 0; i<4; i++){road[0][0][i] = 0;};
    queue<rd> q;
    rd d; d.row = 0; d.col=0; d.dir=-1;
    q.push(d);
    while(!q.empty()){
        d = q.front(); q.pop();
        if(d.row == n-1 && d.col == n-1){
            answer = min(answer, road[n-1][n-1][d.dir]);
            continue;
        }
        for(int next_dir = 0; next_dir < 4; next_dir++){
            int next_r = d.row + dr[next_dir];
            int next_c = d.col + dc[next_dir];
            int cur_cost = road[d.row][d.col][d.dir];
            int next_cost = road[next_r][next_c][next_dir];
            if(0 > next_r || next_r >= n || 0 > next_c || next_c >= n || board[next_r][next_c] == 1 || next_cost < cur_cost) continue;
            
            cur_cost += 100;
            if(d.dir == 0 || d.dir == 2){
                if(next_dir == 1 || next_dir == 3){
                    cur_cost += 500;
                }
            }
            if(d.dir == 1 || d.dir == 3){
                if(next_dir == 0 || next_dir == 2){
                    cur_cost += 500;
                }
            }
            if(next_cost > cur_cost){
                road[next_r][next_c][next_dir] = cur_cost;
                rd n; n.dir = next_dir; n.row = next_r; n.col = next_c;
                q.push(n);
            }
            
        }
        
    }
    
    return answer;
}

 

2. 금과 은 운반하기

이것도 parametric search로 풀어야 하는 문제. 정답에 해당하는 시간은 long long으로 2^64, 매우 큰 값이지만 이분탐색 시 64번만에 해결 가능. 그리고 도시 개수는 10^5으로 조금 작은 편 => 시간으로 이분탐색하고 또한, 결정 문제로 바꾸었을 때 쉽게 풀릴 수 있으며, 가능한 답이 연속적(자연수)이기 때문에 parametric search임을 유추해내야 한다. 다만 결정 문제를 어떻게 풀지 조금 골때렸던 문제 + end를 LLONG_MAX로 두면 안 풀린다...?왤까 ㅋㅋㅋㅋ적당히 10^17로 바꾸면 된다. 왤까.... 그리고 항상 그렇듯 parametric search는 lower bound를 찾는 문제임을 인지!

// 금과 은 운반하기
bool isMoveable(int a, int b, vector<int> g, vector<int> s, vector<int> w, vector<int> t, ll totaltime){
    // 시간이 totaltime
    ll size = g.size();
    ll max_gold = 0, max_silver = 0, max_sum = 0;
    for(int i = 0; i<size; i++) {        
        ll num_move;
        if(totaltime < (ll)t[i]) continue; // 1번도 못옮기는 경우
        else{
            num_move = (totaltime - t[i]) / (2 * t[i]) + 1; // 여러 번 옮길 수 있는 횟수
        }
        ll move_amount = num_move * w[i];
        max_gold += min((ll)g[i], move_amount);
        max_silver += min((ll)s[i], move_amount);
        max_sum += min((ll)g[i] + s[i], move_amount);
    }
    if(max_gold >= a && max_silver >= b && max_sum >= a+b) return true;
    else return false;
}

long long solution(int a, int b, vector<int> g, vector<int> s, vector<int> w, vector<int> t) {
    ll start = 0, end = 1e17, mid;
    
    while(start < end){
        mid = (start + end) / 2;
        if(isMoveable(a, b, g, s, w, t, mid)){ // mid가 옮길 수 있다면
            end = mid;
        } else
            start = mid+1;
    }
    return end;
}

 

3. 최적의 행렬 곱셈

오랜만에 보는 DP. v[i][j]는 행렬 i~j까지 곱했을 때 최솟값이다. 그리고 이 v[i][j]는

i~i * i+1~j

i~i+1 * i+2~j

...

i~j-1 * j*j

의 행렬 곱의 최솟값으로 나온다. 그러면 k는 i부터 j-1까지 돌리면 될 것이다.

// 최적의 행렬 곱셈

#include <string>
#include <limits.h>
#include <algorithm>
#include <vector>

using namespace std;

int solution(vector<vector<int>> matrix_sizes) {
    int size = matrix_sizes.size();
    vector<vector<int>> v(size, vector<int>(size, 0)); // v[i][j] : i~j까지 곱 최솟값

    for(int len = 2; len<=size; len++){
        for(int i = 0; i<size-len+1; i++){
            int j = i + len - 1, min_value = INT_MAX;
            for(int k = i; k<j; k++){
                min_value = min(min_value, v[i][k] + v[k+1][j] + matrix_sizes[i][0] * matrix_sizes[k][1] * matrix_sizes[j][1]);
            }
            v[i][j] = min_value;
        }
    }
    
    
    // v[i][j] : min(i~k * k+1~j)
    
    return v[0][size-1];
}