22.05.06. 풀었던 문제들

1. 양궁 대회

brute-force하게 푼다면 서로 다른 11개의 구역 중 10개를 뽑는 방법(== 동일한 10개의 화살을 11개의 구역에 놓는 경우의 수). 즉 11H10이다. 충분히 계산 가능한 수치. 이 경우 11개의 구역 중 n개를 뽑고, 뽑은 것을 size 11짜리 vector로 변환도 해야하고, 갱신도 신경써줘야 한다. 만약 point 차가 같은 경우는 우선순위가 더 높은 벡터를 정답에 할당해 주어야 하는데, 이에 대한 함수도 만들어 주어야 한다.

즉 만들어야 하는 함수만 'vector 우선순위 계산 함수', '점수 계산 함수', '중복조합 함수'로 다 필요하긴 하지만 상당히 귀찮았다.

// 양궁대회
 
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
vector<int> apeach, answer;
int point_differ = 0;
 
typedef pair<int, int> pii;
 
// a가 우선순위 -> true, b가 우선순위 -> false
bool cmp(vector<int> &a, vector<int> &b){
    //vector 거꾸로 보고 수가 더 커야 함
    for(int i = 10; i>=0; i--){
        if(a[i] > b[i]) return true;
        else if(a[i] == b[i]) continue;
        else return false;
    }
}
 
pii calResult(vector<int> lion){
    int cur_point;
    pii result = {0, 0}; // .first : apeach, .second : lion point
    for(int i = 0; i<=10; i++){
        cur_point = 10-i;
        if(apeach[i] + lion[i] == 0) continue;
        if(apeach[i] >= lion[i]) result.first += cur_point;
        else result.second += cur_point;
    }
    return result;
}
 
// arr : size n, 뽑을 숫자들
// result : size r, 뽑힌 숫자들.
void duplicateCombination(int depth, int r, int prev_idx, vector<int>& arr, vector<int>& result){
    if(depth == r){
        vector<int> lion(11, 0);
        for(int i : result) lion[i]++;
        pii point = calResult(lion);
        int lion_point = point.second, apeach_point = point.first;  
        if(point_differ < lion_point - apeach_point){
            answer = lion;
            point_differ = lion_point - apeach_point;
        }
        if(point_differ == lion_point - apeach_point){
            answer = cmp(lion, answer)? lion : answer;
        }
        return;
    }
    
    for(int i = prev_idx; i<arr.size(); i++){
        result[depth] = arr[i];
        duplicateCombination(depth+1, r, i, arr, result);   
    }
}
 
vector<int> solution(int n, vector<int> info) {
    
    answer = {-1};
    apeach = info;
    vector<int> areas = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    vector<int> combinations(n);
    duplicateCombination(0, n, 0, areas, combinations);
    
    return answer;
}
 
/*
 
11개의 서로 다른 구역 중 n개를 뽑는 방법 (=같은 화살 10개를 11개의 구역에 놓는 방법) -> 중복조합.
-> 11H10
 
*/

 

좀 더 접근한다면, 각 구역에 대해 점수를 얻을지 말지 경우의 수 2개 * 구역 10개 -> 2^10이다.(다만 점수를 얻기 위해서는 잔여 화살 수가 여유가 있어야 한다) 좀 더 적은 수로 계산을 해 볼 수 있다.

 

// 양궁대회
 
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
typedef pair<int, int> pii;
 
vector<int> apeach, answer;
int point_differ = -1;
 
// a가 우선순위 -> true, b가 우선순위 -> false
bool cmp(vector<int> &a, vector<int> &b){
    //vector 거꾸로 보고 수가 더 커야 함
    for(int i = 10; i>=0; i--){
        if(a[i] > b[i]) return true;
        else if(a[i] == b[i]) continue;
        else return false;
    }
}
 
pii calResult(vector<int> lion){
    int cur_point;
    pii result = {0, 0}; // .first : apeach, .second : lion point
    for(int i = 0; i<=10; i++){
        cur_point = 10-i;
        if(apeach[i] + lion[i] == 0) continue;
        if(apeach[i] >= lion[i]) result.first += cur_point;
        else result.second += cur_point;
    }
    return result;
}
 
void DFS(int depth, int max_depth, int num_arrows, vector<int>& lion){
    if(depth == max_depth || num_arrows == 0){
        lion[10] = num_arrows;
        pii point_result = calResult(lion);
        int apeach_point = point_result.first, lion_point = point_result.second;
        if(apeach_point >= lion_point) return;
        
        if(lion_point - apeach_point > point_differ){
            point_differ = lion_point - apeach_point;
            answer = lion;
        }
        else if(lion_point - apeach_point == point_differ){
            answer = cmp(answer, lion)?answer : lion;
        }
        return;
    }
    
    // 점수를 얻을 수 있어서 점수를 얻겠다고 선택하는 경우
    int apeach_point = apeach[depth];
    if(num_arrows >= apeach_point + 1){
        lion[depth] = apeach_point + 1;
        DFS(depth+1, max_depth, num_arrows - apeach_point - 1, lion);
        lion[depth] = 0;
    }
    
    // 점수를 얻을 수 있든 말든 점수를 얻지 않는다고 선택하는 경우
    DFS(depth+1, max_depth, num_arrows, lion);
}
 
vector<int> solution(int n, vector<int> info) {
    apeach = info;
    vector<int> lion(11, 0);
    answer = {-1};
    
    DFS(0, 9, n, lion);
    return answer;
}

 

근데 코드 길이는 비슷하긴 하다. 아무튼 이렇게 2가지 방식으로 풀었다.

​

​

2. 디스크 컨트롤러

SJF를 pq로 구현하면 되는 문제다.

1) 만약 pq에 값이 있다면 값을 빼고 현 시간, 대기시간 등을 계산해 주고,

2) 현 시간보다 짧은 모든 job들을 pq에 넣는다.

3) 만약 pq가 빈 상태라면 다음 job의 입력시간이 현 시간보다 긴 것이다. 이 상태는 무한루프를 돌기 때문에 다음 job의 입력시간을 현 시간으로 수정해 준다.

​

​

3. 정수 삼각형

간단한 DP이다.

​

​

4. 네트워크

간단한 DFS이다.

​