JArchive 프로그래밍 일기

강의실 배정 문제 링크 

리뷰 

'많은'강의를 배정하려면,  강의가 빨리 끝나야 한다. 

따라서 처음에 강의의 종료 시점을 기준으로 오름차순 정렬한다. 

첫 강의의 종료 시점을 cur 에 저장하고, cur보다 크거나 같은 시점에서 시작하는 강의를 배정한다. 

강의를 배정하면 cur가 해당 강의의 종료 시점으로 갱신되야 한다. 

맞았습니다 코드 

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

int n, s, f, cnt;
vector<pair<int,int>> v;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> s >> f;
    v.push_back({f, s}); // 종료가 빠른 수업 먼저.
  }

  sort(v.begin(), v.end());
  int cur = v[0].first; // 첫 종료지점
  cnt = 1; // 강의 개수 

  for(int i = 1 ; i < n; i++){
    if(cur <= v[i].second){
      cur = v[i].first;
      cnt++;
    }
  }
  cout << cnt;
  return 0;
}

제출 기록 

택배 마스터 광우 문제 링크 

리뷰 

택배를 담을 때 레일을 스킵할 수 없음에 주의해야 한다. 

모든 레일의 순서 조합을 검사해야 한다. -> next_permutation() 은 정렬된 자료구조의 모든 순열을 리턴해준다. 

현재 레일까지의 합이 무게제한을 초과한다면, 직전 레일에서 담은 택배까지가 1개의 바구니에 꽉찬 것이다.

따라서 일한 횟수를 1 증가 시키고,  바구니 무게를 0으로 비우면 된다. 

현재 레일까지의 합이 무게제한 범위 내라면,  현재 바구니에 택배를 담는다. 총 누적 무게에도 택배 무게를 증가시킨다. 

일한 횟수 cnt가 목표 횟수 k 번을 만족하면, 총 누적 무게가 최소인지 비교한다. 

맞았습니다 코드 

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

int n, m, k; // 레일 개수, 바구니 무게, 일의 개수
int answer = 2e9;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m >> k;
  vector<int> rail(n, 0);

  for(int i = 0; i < n; i++)  cin >> rail[i];
  sort(rail.begin(), rail.end()); // 레일을 오름차순 정렬 

  do{
     // 종료한 일의 개수, 누적 무게, 현재 바구니 무게, 레일 인덱스
    int cnt = 0, sum = 0, temp = 0, idx = 0; 

    while(cnt < k){ // 일을 총 k번 해야 한다. 
      temp = 0; // 현재 바구니의 무게 0 
      
      while(temp + rail[idx] <= m){
        temp += rail[idx];
        sum += rail[idx];
        idx = (idx + 1) % n; // 레일 인덱스 증가. 레일은 최대 n개니까 %n 해준다. 
      }
      cnt++; // 종료한 일의 개수 증가시킨다. 
    }
    answer = min(sum, answer); // 무게 합이 최소인지 비교 
    
  }while(next_permutation(rail.begin(), rail.end())); // 레일의 모든 순열 만들기 

  cout << answer;
  return 0;
}

제출 기록 

비밀메뉴 문제 링크 

리뷰

사용자 입력 속에 코드가 있는지, 없는지만 구분하면 되는 문제다. 

정규표현식으로 패턴이 있는지 확인하면 되겠다 싶어서 숫자들을 전부 문자로 붙여놨다. 

맞았습니다 코드 

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

int k, m, n, num, cnt;
string code, user_input; // 비밀코드와 사용자입력을 string으로 저장한다 
string answer = "secret";

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> m >> n >> k;

  for(int i = 0; i < m; i++){
    cin >> num;
    code.push_back(num + '0'); // 숫자를 string으로 입력받는다. 
  }
  for(int i = 0; i < n; i++){
    cin >> num;
    user_input.push_back(num + '0');
  }

  smatch match;
  while(regex_search(user_input, match, regex(code))){
    user_input = match.suffix();
    cnt++;
  }

  if(cnt == 0) answer = "normal";
  cout << answer;
  return 0;
}

제출 기록 

금고털이 문제 링크 

리뷰 

가격이 가장 비싼 것 부터 담아야 한다. 

따라서 '가격' 을 우선으로 정렬해야 한다. 

담았을 때마다 가격은 더해주되, 바구니 무게 w는 무게만큼 빼준다. 

바구니에 담을 수 있는 무게 w가 0이 되면 종료시킨다. 

맞았습니다 코드 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int w, n, a, b;
int answer;
vector<pair<int,int>> v;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> w >> n;
  for(int i = 0; i < n; i++){
    cin >> a >> b; // {무게, 가격}
    v.push_back({b, a}); // {가격, 무게}
  }

  sort(v.begin(), v.end(), greater<>());
  for(auto a : v){
    int small_weight = min(w, a.second);
    answer += (small_weight * a.first);
    w -= small_weight;
    if(w == 0) break;
  }
  cout << answer;
  return 0;
}

제출기록

GBC 문제 링크 

리뷰 

0부터 99까지의 거리는 고정되어 있다. (이게 핵심인 것 같다.)

따라서 각 지점마다의 속도 제한을 입력받고, 각 지점마다의 검사 속도를 입력 받는다. 

벡터 limit와 벡터 test를 0부터 99까지 전부 비교한다. 

제한 속도 보다 제일 크게 차이 나는 지점을 답으로 낸다. 

맞았습니다 코드 

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

int n, m, a, b, answer;
vector<int> limit, test;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m;

  while(n--){ // 주어진 속도 제한 
    cin >> a >> b;
    for(int i = 0; i < a; i++) limit.push_back(b);
  }
  while(m--){ // 검사할 속도 목록 
    cin >> a >> b;
    for(int i = 0; i < a; i++) test.push_back(b);
  }

  for(int i = 0; i < 100; i++){
    answer = max(answer, test[i] - limit[i]);
  }

  cout << answer;
  return 0;
}

제출 기록 

8단 변속기 문제 링크 

리뷰 

오름차순인지, 내림차순인지, 정렬 안됬는지만 확인하는 문제였다. 

정렬이 됬다면 각 숫자들의 차가 1이다. 정렬이 안된 mixed라면 이를 만족하지 못한다. 

맞았습니다 코드 

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

bool check_flag = true;
string answer = "mixed";
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  vector<int> v(8);
  cin >> v[0];
  for(int i = 1; i < 8; i++){
    cin >> v[i];
    if(abs(v[i-1] - v[i]) != 1){ check_flag = false; break; }
  }

  if(check_flag){
    answer = (v[0] == 8) ? "descending" : "ascending";
  }

  cout << answer;
  return 0;
}

입국심사 문제 링크 

리뷰 

이분 탐색은 원소들이 정렬된 상태에서 탐색이 가능하므로 sort() 해준다. 

처음에 틀린 부분은, 데이터 타입 때문이다.

이분 탐색의 시작시간과 종료시간 초기화에서 long long 으로 초기화가 안되어 있어서 틀렸다. 

함수의 파라미터 n과 벡터 times는 전부 int 형이다. 

탐색의 최대시간을 초기화할 때, int 벡터의 마지막 인덱스 값을 참조하니까, 따로 (long long)형변환을 해줘야 한다. 

long long solution(int n, vector<int> times) {

  long long max_time = (long long)times[size_of_times-1] * n; // 가장 오래걸리는 시간
}

아래 코드처럼 짜면, max_time변수가  int 곱하기 int 값으로 초기화 된다.

그래서 max_time이 int 형이 된다.  

long long solution(int n, vector<int> times) {

  long long max_time = times[size_of_times-1] * n; // 가장 오래걸리는 시간
}

심사할 사람의 최소값은 1명. 심사 시간 최소값은 1분이다.

따라서 탐색의 최소 시간 min 은 1 이다. 

심사할 사람의 최대값 1,000,000,000명. 심사 시간 최대값은 1,000,000,000분이다. 

심사 시간 최대값 max는 주어진 배열에서 가장 큰 숫자로 초기화 한다.

min,max의 중간값 mid 시간에 n명을 다 처리할 수 있는지 계산한다.

mid 시간 동안 각 심사대는 몇 명을 처리할 수 있는지 계산해서 ( mid_time / times[i] ) man_cnt에 센다.

주어진 시간 안에 man_cnt명을 처리했을 때 n보다 크거나 같아야 한다.

이 때의 mid값이 최소 이면 answer에 저장한다. 

맞은 코드 (테스트케이스 10개 중 10개 O)

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long solution(int n, vector<int> times) {

  int size_of_times = times.size();
  sort(times.begin(), times.end());

  long long min_time = 1L; // 가장 짧은 시간
  long long max_time = (long long)times[size_of_times-1] * n; // 가장 오래걸리는 시간
  long long mid_time = (min_time + max_time) / 2; // 중앙값
  long long answer = max_time;

  while(min_time <= max_time){

    mid_time = (min_time + max_time) / 2;
    long long man_cnt = 0;
    for(auto t : times) { // mid_time 동안 처리할 수 있는 사람 수를 센다.
      man_cnt += mid_time / t;
    }

    if(n <= man_cnt){
      answer = min(answer, mid_time);
      max_time = mid_time - 1;
    }
    else {
      min_time = mid_time + 1; // 시간이 부족
    }
  }
  return answer;
}

틀린 코드  (테스트케이스 10개 중 9개 O)

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long solution(int n, vector<int> times) {

  int size_of_times = times.size();
  sort(times.begin(), times.end());

  long long min_time = 1L; // 가장 짧은 시간
  long long max_time = times[size_of_times-1] * n; // 가장 오래걸리는 시간
  long long mid_time = (min_time + max_time) / 2; // 중앙값
  long long answer = max_time;

  while(min_time <= max_time){

    mid_time = (min_time + max_time) / 2;
    long long man_cnt = 0;
    for(auto t : times) { // mid_time 동안 처리할 수 있는 사람 수를 센다.
      man_cnt += mid_time / t;
    }

    if(n <= man_cnt){
      answer = min(answer, mid_time);
      max_time = mid_time - 1;
    }
    else {
      min_time = mid_time + 1; // 시간이 부족
    }
  }
  return answer;
}