JArchive 프로그래밍 일기

수퍼바이러스 문제 링크 

리뷰 

바이러스가 처음에 K마리 있고, N초 동안 증가율 P배씩 증가한다. 

주어진 증가율 P배는 0.1초당 증가율이고, 제한 시간 N초는 1초 단위다. 이 단위 차이를 반영하자. 

0.1초당 P배씩 증가하니까 1초당 바이러스는 10 * P배씩 증가한다.  

증가율 P가 아니라 주어진 N초에 10을 곱해줘도 된다.

N초 동안 P배씩(0.1초당) 증가하므로,  10 * N초 동안 P배씩 증가하는 것과 같다. 

N초는 long long 자료형이니까 매우 큰 숫자가 주어진다. 

따라서 분할정복 함수 cal() 을 구현한다. 

몇 제곱인지를 구하는 것이니까 몇승을 하는지 재귀호출로 구할 수 있다. 

1승이면 p배를 리턴한다. 

ll cal(ll cnt){ // cnt 초 동안  x배
  if(cnt == 1) return p;

2승이면 1승 * 1승을 재귀호출해서 구한 값으로 리턴한다. 

  ll result = cal(cnt/2);

  result = result * result % MOD; // 짝수 승

홀수 승이면, /2 승 * /2 승 * 1승 해주면 된다. 

ex) 5승 ==> 2승 * 2승 * 1승 

if(cnt % 2 == 1) result = (result * p) % MOD; // 홀수 승은 p를 한번 더 곱한다.

답을 10000007로 나눈 나머지를 리턴해야 하니까 곱할 때 마다 MOD로 나눈 나머지를 저장하자. 

맞았습니다 코드 

#include<iostream>
#define MOD 1000000007
#define ll long long
using namespace std;

ll k, p, n;

ll cal(ll cnt){ // cnt 초 동안  x배
  if(cnt == 1) return p;
  ll result = cal(cnt/2);

  result = result * result % MOD; // 짝수 승
  if(cnt % 2 == 1) result = (result * p) % MOD; // 홀수 승은 p를 한번 더 곱한다.
  return result;
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> k >> p >> n;

  // 0.1초 마다 p배 -> 1초마다 p*10배 -> 10*N초 동안 p배
  ll answer = (cal(10 * n) * k) % MOD;
  cout << answer;
  return 0;
}

제출기록 

강의실 배정 문제 링크 

리뷰 

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

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

첫 강의의 종료 시점을 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;
}