JArchive 프로그래밍 일기

지도 자동 구축 문제 링크 

리뷰 

점 개수가 늘어나는 규칙보다는 전체 개수의 규칙을 셌다. 

0단계에서 한 변의 점 개수는 2개다. 

1단계에서 한 변의 점 개수는 3개다. 

2단계 에서는 5개, 3 단계에서는 9개가 된다. 

사각형의 전체 점 개수는 한 변의 점 개수의 제곱이다. 

2, 3, 5, 9  ==>  2의 0승 1승 2승 만큼 증가한다.  여기서 DP를 이용해 짰다. 

맞았습니다 코드 

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

int n;
ll D[10];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  D[0] = 2, D[1] = 3;
  ll addnum = 1;
  for(int i =2; i <= n; i++){
    addnum *= 2;
    D[i] = D[i-1] + addnum;
  }
  cout << D[n] * D[n];
  return 0;
}

제출기록

우물 안 개구리 문제 링크 

리뷰 

힘을 저장하는 배열 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;
}

제출기록 

스마트 물류 문제 링크 

리뷰 

라인 길이가 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;
}

제출 기록