JArchive 프로그래밍 일기

택배 마스터 광우 문제 링크 

리뷰 

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

모든 레일의 순서 조합을 검사해야 한다. -> 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;
}

이중우선순위큐 문제링크 

리뷰 

최소값 삭제와 최대값 삭제를 위해 매번 큐의 정렬을 다시 할 수 는 없다. 그래서 우선순위큐 2개를 뒀다. 

우선순위큐의 기본 정렬은 less라서 오름차순이다. 

오름차순 정렬하는 최소값 큐 min_pq

내림차순 정렬하는 최대값 큐 max_pq 

큐 사이즈를 관리하는 변수가 0이 되면, 큐 2개 다 비워줘야하는데! 이 부분을 빠뜨려서 다른 분 코드를 참고했다. 

1. priority_queue 2개 사용한 코드 

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

priority_queue<int, vector<int>, greater<>> min_pq;
priority_queue<int, vector<int>, less<>> max_pq;
int pq_size; // 큐의 사이즈 관리

vector<int> solution(vector<string> op) {
  vector<int> answer = {0, 0};

  for(auto s : op){
    string order = s.substr(0, 1); // 명령 문자 I 또는 D 

    int num = stoi(s.substr(2, s.size())); // 숫자부분  

    if(order == "I") {
      min_pq.push(num);
      max_pq.push(num);
      pq_size++;
    }
    else if(pq_size > 0 && order == "D"){

      (num == -1) ? min_pq.pop() : max_pq.pop();
      pq_size--;

      if(pq_size == 0){
        while(!min_pq.empty()) min_pq.pop();
        while(!max_pq.empty()) max_pq.pop();
      }
    }
  }

  if(!min_pq.empty() && !max_pq.empty()) answer = {max_pq.top(), min_pq.top()};
  return answer;
}

풀고 나니깐 다른 분들 코드에 set이 보이길래 multiset으로 풀어도 됬겠다 싶었다.  

2. vector 로 푼 코드 

앞, 뒤에서 하나씩 erase로 지워주기만 하면 되니까. vector로도 괜찮다. 

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

vector<int> solution(vector<string> op) {
  vector<int> answer = {0,0};
  vector<int> v;

  for(auto s : op){
    string order = s.substr(0, 1); // 명령
    int num = stoi(s.substr(2)); // 숫자

    if(order == "I") {
      v.push_back(num);
      sort(v.begin(), v.end(), greater<>()); // 푸시하고 바로 정렬.
    }
    else {
      if(v.size() == 0) continue;

      (num == -1) ? v.erase(v.end()-1) : v.erase(v.begin());
    }
  }

  if(!v.empty()) {
    answer.clear();
    answer = {v[0], v[v.size()-1]};
  }
  return answer;
}

정수 삼각형 문제 링크 

리뷰 

등굣길 문제와 비슷하게 느껴졌다. 

삼각형의 가로 세로는 500이하라는 조건이 있으니까 점화식 값을 저장할 DP배열 크기를 501, 501로 잡아둔다. 

최대 합을 구하려면, 반드시 1층부터 마지막층까지 이동해야 한다. 

모든 층의 첫번째 칸은 바로 위에서만 올 수 있다. 

모든 층의 마지막 칸은 왼쪽 위에서만 올 수 있다. 

이 2가지 예외를 제외하고, 아래와 같은 점화식을 만족한다. 

D[a][b] = max(D[a-1][b] , D[a][b-1]) + 현재칸의 값 A[a][b]

맞았습니다 코드 

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

int D[501][501];

int solution(vector<vector<int>> t) {
  int answer = 0;

  D[0][0] = t[0][0];
  D[1][0] = t[1][0] + D[0][0];
  D[1][1] = t[1][1] + D[0][0];

  int height_t = t.size();

  for(int i = 2; i < height_t; i++){

    for(int j = 0; j <= i; j++){
      if(j == 0) D[i][j] = t[i][j] + D[i-1][j];
      else if(j == i) D[i][j] = t[i][j] + D[i-1][i-1];
      else{
        D[i][j] = t[i][j] + max(D[i-1][j], D[i-1][j-1]);
      }
    }
  }

  for(int i = 0; i < height_t; i++){
    answer = max(answer, D[height_t-1][i]);
  }

  return answer;
}

등굣길 문제링크 

리뷰 

최단 경로를 세야 하니까 오른쪽 또는 아래로만 이동해야 한다. 

그래서 특정 지점까지 몇번을 거쳐 가는지 점화식을 세야 한다. 

웅덩이가 있으면 최단경로를 세면 안되니까 처음부터 -1로 초기화 해둔다. 

현재 지점 기준으로 위, 또는 왼쪽의 최단경로를 기반으로  현재 지점의 최단경로를 계산한다. 

인덱스에 음수가 발생하지 않도록 (1, 1)을 시작점으로 두고 (1, 1)의 최단경로를 1로 초기화한다. 

핵심 코드는 아래와 같다

temp_a = (위칸이 음수가 아니라면, ) D[a-1][b] 
temp_b = (왼쪽칸이 음수가 아니라면, ) D[a][b-1] 

D[a][b] = (temp_a + temp_b) % div_num;

맞았습니다 코드 

#include <string>
#include <vector>

using namespace std;
int D[101][101]; // 최단거리를 저장할 배열
int div_num = 1000000007;

int solution(int m, int n, vector<vector<int>> puddles) {

  for(auto v : puddles){
    D[v[1]][v[0]] = -1; // 물웅덩이를 -1로 초기화
  }
  D[1][1] = 1;

  for(int i = 1; i <= n; i++){ // n: 행
    for(int j = 1; j <=m; j++){ // m: 열
      if(D[i][j] == -1) continue;
      int temp_a = 0, temp_b = 0;

      if(D[i-1][j] != -1) temp_a = D[i-1][j];
      if(D[i][j-1] != -1) temp_b = D[i][j-1];

      D[i][j] += (temp_a + temp_b) % div_num;
    }
  }

  return D[n][m];
}

문제 링크 

리뷰 

처음에 감을 못잡은 문제... 어떤 파라미터 넘겨서 탐색해야되지? 다음에 다시 풀어봐야겠다. 

맞았습니다 코드 

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

int global_N, target_number;
int max_cnt = 8;
int min_cnt = 1 + max_cnt;

void dfs(int cur_num, int cnt){ // (현재 숫자, N을 사용한 개수)
  if(cnt > max_cnt) return;
  else if(cur_num == target_number){
    min_cnt = min(cnt, min_cnt);
    return;
  }

  int n = 0;  // 계산할 숫자 n 
  for(int i = 1; i <= 6; i++){ // N을 1개~6개 사용가능
    // 계산할 숫자 n -> N, NN, NNN
    n = n*10 + global_N;
      
    dfs(cur_num + n, cnt + i);
    dfs(cur_num - n, cnt + i);
    if(cur_num != 0 || cnt > 8){
      dfs(cur_num * n, cnt + i);
      dfs(cur_num / n, cnt + i);
    }
  }
}

int solution(int N, int number) {
  global_N = N;
  target_number = number;
  dfs(0, 0);
  return (min_cnt == 9) ? -1 : min_cnt;
}