JArchive 프로그래밍 일기

문제 링크 

중복 원소를 오름차순으로 저장하는 multiset 으로 풀었다.  

원소를 지우기 전에, 사이즈를 꼭 체크하도록 하자..

다시 풀어볼 문제. 

"맞았습니다" 코드 링크 

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

int T, k, n;
char ch;

void solve(){

  multiset<int> ms;
  cin >> k;

  while(k--){
    cin >> ch >> n;
    if(ch == 'I') ms.insert(n);
    else if(ms.size() > 0){
      if(n > 0){ // 최댓값 삭제
        auto iter = ms.end();
        ms.erase(--iter);
      }else ms.erase(ms.begin());
    }
  }

  if(ms.size() == 0) cout << "EMPTY\n";
  else {
    auto iter = ms.end();  --iter;
    cout << *iter << ' ' << *ms.begin() << '\n';
  }
  return;
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> T;
  while(T--){
    solve();
  }
  return 0;
}

multiset reference 

multiset 정리 포스팅 

문제 링크 

"2의 n-1 승씩 사분면을 좁혀나가면 풀릴것 같은데.. " 하다가 30분째 안풀려서 다른 분들의 풀이 포스팅을 읽고 방법을 이해할 수 있었다. 

재귀를 이용해서 사분면을 좁혀나가는데,

사분면의 한 변 길이를 이용해서 사분면이 포함하는 칸의 개수를 센다.

그래서 1, 2, 3, 4 사분면마다 더해주는 숫자가 다르다.

다시 풀어볼 문제다. 

"맞았습니다" 코드 링크 

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

int N, r, c, answer;

void rec(int n, int row, int col){

  if(n == 0) return;
  int len = pow(2, n-1);  // 사분면 한 변의 길이
  int square_cnt  = len * len;  // 사분면 하나가 포함하는 칸 수

  if(row / len == 0 && col / len == 0){ // 1사분면
    rec(n-1, row % len, col % len);
  }
  else if(row / len == 0 && col / len == 1){ // 2사분면
    answer += square_cnt;
    rec(n-1, row % len, col % len);
  }
  else if(row / len == 1 && col / len == 0){ // 3사분면
    answer += square_cnt * 2;
    rec(n-1, row % len, col % len);
  }
  else if(row / len == 1 && col / len == 1){ // 4사분면
    answer += square_cnt * 3;
    rec(n-1, row % len, col % len);
  }
}

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

  cin >> N >> r >> c;

  rec(N, r, c);
  cout << answer;

  return 0;
}

그림 설명이 된 참고 포스팅 

참고 포스팅 

  for(int k = 0; k < n; k++){ // 거쳐가는 정점
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
      }
    }
  }

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

int n;
int arr[102][102];

void floyd() {

  for(int k = 0; k < n; k++){ // 거쳐가는 정점
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
      }
    }
  }
}
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 >> arr[i][j];
      if(arr[i][j] == 0) arr[i][j] = INF;
    }
  }
  floyd();
  for(int i = 0; i < n; i++){
    for(int j = 0; j< n; j++){
      if(arr[i][j] == INF) cout << 0 << ' ';
      else cout << 1 << ' ';
    }
    cout << '\n';
  }

  return 0;
}

플로이드 와샬 알고리즘 (나동빈님 블로그)

문제 링크 

n <= m 조건을 가지고 있고,  다리를 만드는 경우의 수를 센다. 

문제 하단에 '다이나믹 프로그래밍' 이라고 힌트가 써있길래 2차원 배열로 풀 수 있었다. 

먼저 n과 m이 같은 수라면 경우의 수는 전부 1개다.  

n == 1 이면, m이 뭐든간에 경우의 수는 m개다. 

입력을 받기 전에, DP배열을 미리 채워놓는다. 

a[2][2] = 1 

a[2][3] = a[1][1] + a[1][2]

a[2][4] = a[1][1] + a[1][2] + a[1][3] 

a[i][j] = a[i-1][1] + a[i-1][1] + .... + a[i-1][j-1]

"맞았습니다" 코드 링크 

/** 다리 놓기
 * https://www.acmicpc.net/problem/1010
 * http://boj.kr/2dd342c6f44849369f678383dea56dbf
 * */
#include <bits/stdc++.h>
using namespace std;

int t, n, m;
int a[32][32];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  for(int i = 1; i <= 30; i++){
    a[i][i] = 1; a[1][i] = i;
  }
  for(int i = 2; i < 30; i++){
    for(int j = i+1; j < 30; j++){
      for(int k = 1; k < j; k++){
        a[i][j] += a[i-1][k];
      }
    }
  }
  cin >> t;
  while(t--){
    cin >> n >> m;
    cout << a[n][m] << '\n';
  }
  return 0;
}

문제 링크 

입력 되는 모든 문자열의 길이가 같다. 

1. 따라서 문자열 길이의 처음부터 끝까지를 비교하는 이중반복문으로 풀었다. 

2. 모든 문자열을 한 번에 입력받지 않고, 그때 그때 첫 문자열과 비교하여 답을 내는 방법으로도 풀었다. 

"맞았습니다" 코드 링크 1

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

int n, h, idx;
vector<string> v;
string input, answer;
bool check_flag = true;

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

  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> input;
    v.push_back(input);
  }
  int len = v[0].length(); // 문자열 길이 (모두 같다)
  int vsize = v.size();

  for(idx = 0; idx < len; idx++){
    check_flag = true;
    for(h = 0; h < vsize-1; h++) { // 모든 문자열의 인덱스 h자리가 같은지.
      if (v[h][idx] != v[h + 1][idx]) {
        check_flag = false; break;
      }
    }
    check_flag ? answer += v[h][idx] : answer += "?";
  }
  cout << answer;
  return 0;
}

"맞았습니다" 코드 링크2

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

int n, h, idx;
string tempstr, answer;

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

  cin >> n >> answer;
  while(n--) {
    cin >> tempstr;
    for(int i = 0; i < tempstr.size(); i++)
      if(tempstr[i] != answer[i]) answer[i] = '?';
  }
  cout << answer;
  return 0;
}