JArchive 프로그래밍 일기

문제 링크 

"맞았습니다" 코드 링크

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

int n, num, i, mo, ja;

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

  cin >> n;

  while(num < n){ // i: 1, 2, 3, 4, ...
    i++;
    num += i;
  }
  // while문 종료 직후, num은 n보다 같거나 큰 수가 되어 있다.
  int diff = num - n; // 라인 시작점부터 이동할 숫자

  if(i % 2){  // 홀수 라인 - 밑에서 대각선으로 위로 숫자 변화
    ja = 1 + diff;
    mo= i - diff; 
  }
  else { // 짝수 라인 - 위에서 왼쪽 대각선으로 아래로 숫자 변화
    ja = i - diff; 
    mo = 1 + diff;
  }

  cout << ja << '/' << mo;
  return 0;
}

리뷰 

1. 대각선 라인을 기준으로 생각한다.  순서를 떠나서, 그림 그대로 바라보면 아래와 같다. 

[홀]  1번째 라인 : 1/1

[짝]  2번째 라인 : 2/1 , 1/2 

[홀]  3번째 라인 : 3/1, 2/2, 1/3

[짝]  4번째 라인 : 4/1, 3/2, 2/3, 1/4

2. 짝수 라인과 홀수라인에서 분자와 분모가 어떻게 변하는지 보면 규칙을 발견할 수 있다. 

짝수 2번째 라인 :  2 / 1  ,  1 / 2 

=> 분자 : 시작 2, 종료 1  (분자는 감소)

=> 분모 : 시작 1, 종료 2  (분모는 증가)

홀수 3번째 라인 :  3 / 1  ,  2 / 2,  1 / 3 

=> 분자 : 시작 3, 종료 1

=> 분모 : 시작 1, 종료 3 

3. 주어진 숫자 n이 홀수라인에 속하는지, 짝수 라인에 속하는지 확인해야 한다. 

  cin >> n; // n 번째 칸이 홀수 라인인지 짝수 라인인지 확인하기.

  while(num < n){ // i: 1, 2, 3, 4, ...
    i++;
    num += i;
  }

1번째는 1개 분수가 있다.

2번째 라인에는 2개 분수가 있다. num에 1, 2, 3, 4 .. 씩 더해주며 몇 번째 라인에 속한건지 반복문 돌린다.  

반복문 끝나면, 숫자 n은 i 번째 라인에 속한다. 

while문 종료 직후, num은 n보다 같거나 큰 수가 되어 있다. 반복문 마지막에 무조건 i를 더하고 종료하기 때문이다. 

4. offset 확인한다.

diff 변수 :  라인 내부에서 몇 번째 숫자인지를 나타낸다. 

i 가 짝수인 경우.

짝수 라인에서 분자는  i에서 시작한다. --> i - diff 

짝수 라인에서 분모는 1에서 시작한다. --> 1 + diff 

짝수 2번째 라인 :  2 / 1  ,  1 / 2 

=> 분자 : 시작 2, 종료 1  (분자는 감소)

=> 분모 : 시작 1, 종료 2  (분모는 증가)

  if(i % 2){  // 홀수 라인 - 밑에서 대각선으로 위로 숫자 변화
    ja = 1 + diff; // 분모가 1로 시작 i로 종료.
    mo= i - diff; // 분자가 i로 시작, 1로 종료.
  }
  else { // 짝수 라인 - 위에서 왼쪽 대각선으로 아래로 숫자 변화
    ja = i - diff; // 분모 i로 시작 1로 종료
    mo = 1 + diff; // 분자 1로시작 i로 종료
  }

풀릴 듯 안풀려서 고생했다.  나중에 다시 풀기!!!

참고 포스팅

문제 링크

숫자를 최소값으로 만드려면 음수가 많아야 한다. 그래서 '-' 이후에 나오는 숫자들은 모두 뺀다. 

"맞았습니다" 코드 링크 

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

string input, temp_st;
int num;
bool minus_flag;

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

  cin >> input;
  int len = input.size();

  for(int i = 0; i <= len; i++){
    if(input[i] == '-' || input[i] == '+' || i == len){
      (minus_flag) ? num -= stoi(temp_st) : num += stoi(temp_st);
      temp_st = "";
    }else {
      temp_st += input[i];
    }
    if(input[i] == '-') minus_flag = true; // '-'이 다음에 나오는 숫자는 모두 뺀다
  }

  cout << num;
  return 0;
}

문제 링크 

동전을 최소 갯수로 사용해서 합이 K원이 되야 한다. 

동전을 사용할 수 있으려면, K원이 동전값으로 나누어 떨어져야 한다. 

"맞았습니다" 코드 링크

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

int n, k, tempsum, cnt;
int coin[11]; // 동전 종류

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

  cin >> n >> k;
  for(int i = 0; i < n; i++) cin >> coin[i];

  for(int i = n-1; i >= 0; i--){
    cnt += (k / coin[i]);
    k = k % coin[i]; // 나머지 금액
  }
  cout << cnt;
  return 0;
}

문제 링크 

절대값이 가장 작은 것을 리턴해야 하니까 자동 정렬되는 priority queue를 썼다. 

pair<int,int> 는 first를 기준으로 정렬된다. 하지만 first가 똑같으면 second를 기준으로 정렬된다. 

따로 정렬함수를 정의하지 않아도 문제 조건에 맞게 정렬됬다. 

"맞았습니다" 코드 링크 

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

int n, input;

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

  priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
  // <절대값, 원본값>

  cin >> n;
  while(n--){
    cin >> input;
    if(input == 0){
      if(pq.empty()) cout << 0 << '\n';
      else {
        cout << pq.top().second << '\n';
        pq.pop();
      }
    }else{
      pq.push({abs(input), input});
    }
  }
  return 0;
}

문제 링크 

중복 원소를 오름차순으로 저장하는 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;
}

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