JArchive 프로그래밍 일기

우물 안 개구리 문제 링크 

리뷰 

힘을 저장하는 배열 power 과, 최고라고 생각한다/안한다 를 저장하는 iambest 배열을 따로 만들었다. 

처음에는 모두 다 '나는 최고'라고 생각하도록 iambest를 1로 초기화 했다. 

친분관계를 순회하면서 자신보다 힘쎈 사람인지 power 배열 값으로 비교한다. 

힘이 같거나 힘이 약하면 iambest 값을 0 으로 바꾼다. 

마지막에 iambest 가 1인 사람만 카운팅 해서 답을 낸다. 

코드를 짜고 나니깐 이차원 배열로 해도 상관없을 것 같다는 생각이 들었다. 

맞았습니다 코드 

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

int n, m, a, b, answer;

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

  cin >> n >> m;

  vector<bool> iambest(n+1, 1);
  vector<int> power(n+1, 0);

  for(int i = 1; i <= n; i++) cin >> power[i];

  while(m--){
    cin >> a >> b;
    if(power[a] < power[b]){
      iambest[a] = 0;
    }else if(power[a] > power[b]){
      iambest[b] = 0;
    }else{
      iambest[a] = 0;
      iambest[b] = 0;
    }
  }
  // 아직 1인 사람(최고라고 생각) 카운팅
   for(int i = 1; i <= n; i++) if (iambest[i] > 0) answer++;
   
  cout << answer;
  return 0;
}

제출 기록 

H-클린알파 문제 링크

리뷰

바이러스가 1초, 2초, 3초 ... 1초 간격으로 들어온다. 

바이러스가 들어올 때는 증가율을 신경쓰지않고 개수 그대로 더해줘야 한다. 

이미 있었던 바이러스에만 증가율 p를 곱해주면 된다. 

맞았습니다 코드 

#include <bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;

ll p, n, total_cnt, num;
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> p >> n;
  while(n--){
    cin >> num; // 바이러스 개수 입력받기
    total_cnt = (total_cnt * p + num) % MOD;
  }
  cout << total_cnt;
  return 0;
}

제출기록 

문제 링크 

리뷰 

처음에 이중 for문으로 하다가 시간초과나서 틀렸다. 

left 부터 right까지의 인덱스 찾기

일차원 배열일 때, 행 하나씩 0,1,2,3,4,5 의 연속적인 값의 인덱스를 갖는다. 

해당 인덱스의 값 찾기

n = 4 일 때 , 1, 2, 3, 4 값을 가지는 칸은 이중 for문으로 이차원 배열을 순회할 때의 (i, j) 좌표를 떠올리자. 

i와 j를 비교했을 때, 큰 값을 '값'으로 가진다. 

맞았습니다 코드 

#include <string>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

vector<int> answer;
vector<int> v;
vector<int> solution(int n, long long left, long long right) {

  for(ll i = left; i <= right; i++){
    answer.push_back(1+ max(i / n, i % n));
  }
  return answer;
}

스마트 물류 문제 링크 

리뷰 

라인 길이가 20,  현재 로봇의 좌표가 i = 1이고, 잡을 수 있는 범위가 k = 2 라면, 

검사해야할 좌표는 0, 2, 3 이다. 

유효범위인지 확인해야 한다. => 확인한 좌표가 0이상, 20 미만인지. 

유효범위 인데, 'H' 물건을 잡았다면, 다시 잡을 수 없도록 값을 바꿔놔야 한다.  line[j] = 'X' 

맞았습니다 코드 

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

int n, k, answer;
string line;
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> k >> line;

  for(int i = 0; i < n; i++) {
    if('P' == line[i]){ // 로봇이라면, 양쪽을 확인
      for(int j = i-k; j <= i+k; j++){ // i 기준 양쪽을 본다.
        if(i == j || j < 0 || j >= n) continue;// 유효인덱스 검사
        if(line[j] == 'H') {
          line[j] = 'X';  answer++; break; // 선택 표시하고 개수 증가
        }
      }
    }
  }
  cout <<  answer;
  return 0;
}

제출기록

징검다리 문제 링크 

리뷰 

최장증가수열 코드를 떠올려서 풀었다. 

최장증가수열 풀이법은 이 포스팅에 그림이 잘 그려져 있다.

맞았습니다 코드 

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

int n, num;
vector<int> v;
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  cin >> num;
  v.push_back(num);

  for(int i = 1; i < n; i++){
    cin >> num;

    for(int j = v.size()-1; j >= 0; j--){
      if(v[j] < num){
        if(j == v.size()-1) v.push_back(num); // 가장 크니까 push 
        else v[j+1] = num; // 값 교체 
        break;
      }
      if(j == 0) v[0] = num;
    }
  }
  cout << v.size();
  return 0;
}

제출 기록 

소프티어 성적평균 문제 링크 

리뷰 

algorithm 헤더에서 제공하는 accumulate 로 풀었다. 

특정 인덱스 x, 부터 y까지의 합을 리턴해주는데, 초기값을 마지막 파라미터에 설정해줄 수 있다. 

맞았습니다 코드 

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

int n, k, num, a, b;
vector<int> score;

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

  cin >> n >> k;
  while(n--){
    cin >> num;  score.push_back(num);
  }
  while(k--){
    cin >> a >> b;
    double cnt = (b-a) + 1;
    double sum = accumulate(score.begin() + a-1, score.begin() + b, 0);
    
    double res = (double) sum / cnt;
    res = ceil(res * 100) / 100;
    printf("%.2f\n", res);
  }
  return 0;
}

제출기록

문제 링크 

리뷰 

백준의 토마토? 유기농배추? 문제와 비슷했다. 

지도를 전체 순회 하되, 장애물을 발견하면 그 좌표에서 BFS 탐색한다. 

지도 배열 obs_map 과 방문 배열 check는 전역변수로 선언한다. 

왜냐하면 장애물을 발견했을 때, 그 위치에서 다시 BFS를 할 이유가 없기 때문이다.

현재 좌표가 첫 방문이고 장애물이 있으면 BFS를 돌린다. 

BFS에서 리턴할 장애물 블록 개수 cnt 변수는, 장애물 1개로 탐색을 시작했으니까 반드시 1로 초기화한다. 

BFS 시작 좌표를 방문배열 true로 해주고, 탐색좌표 큐에 좌표를 push한다.  

다음 좌표를 탐색할 때, 4방향을 모두 확인한다. 

정상 범위인지 (인덱스가 유효한지), 이미 방문했는지, 도로인지 확인한다. 

장애물을 발견했다면 방문배열 true로 해주고 cnt를 증가시키고 탐색좌표 큐에 넣는다. 

맞았습니다 코드 

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

int n; // 지도의 크기
char ch;
char obs_map[26][26];
vector<int> answer;
bool check[26][26];

int nx[4] = {1, -1, 0, 0};
int ny[4] = {0, 0, 1, -1};

bool check_boundary(int x, int y){ // 정상범위인지 확인
  return (x >= 0 && x < n && y >= 0 && y < n);
}

int BFS(int i, int j){
  int cnt = 1;

  queue<pair<int,int>> qu;
  check[i][j] = true;
  qu.push({i, j});

  while(!qu.empty()){
    int cur_x = qu.front().first;
    int cur_y = qu.front().second;
    qu.pop();

    for(int i = 0; i < 4; i++){
      int next_x = nx[i] + cur_x;
      int next_y = ny[i] + cur_y;

      if(!check_boundary(next_x, next_y)) continue; // 정상범위
      if(check[next_x][next_y]) continue; // 이미 방문
      if(obs_map[next_x][next_y] == '0') continue;  // 도로
      else{
        check[next_x][next_y] = true;
        qu.push({next_x, next_y});
        cnt++;
      }
    }
  }
  return cnt;
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n; // 지도의 크기
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      cin >> ch;
      obs_map[i][j] = ch;
    }
  } // 입력받기 끝


  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(obs_map[i][j] == '1' && !check[i][j]){
        int cnt = BFS(i, j);
        //cout << "cnt:" << cnt << '\n';
        answer.push_back(cnt);
      }
    }
  }

  sort(answer.begin(), answer.end());
  cout << answer.size() << '\n';
  for(auto i : answer) cout << i << '\n';

  return 0;
}

제출 기록 

수퍼바이러스 문제 링크 

리뷰 

바이러스가 처음에 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;
}

제출 기록