JArchive 프로그래밍 일기

기타레슨 문제 링크

리뷰 

강의 전부가 M장 블루레이에 담겨야 한다. 따라서 블루레이 크기가 최소 몇분이 되야 하는지 찾는 문제다. 

이분탐색의 타겟은 블루레이의 크기다. 

블루레이의 크기는 최소 1분, 최대 모든 강의의 크기 중에서 탐색할 수 있다.

주의할 점은 블루레이의 크기보다 강의 하나의 크기가 큰 경우도 있을 수 있다는 점이다. 

main 함수 while문에서 이분탐색을 한다.

if문의 b_search() 함수는 블루레이가 mid크기의 강의를 담을 수 있다고 했을 때, M장의 블루레이만으로 모든 강의를 담을 수 있는지 확인하는 bool 함수다. 

이분탐색 문제는 무엇을 주제로 이분탐색 할 지를 잘 생각하고 시작해야되니까 연습이 좀 필요한 것 같다. 

"맞았습니다" 코드 

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

int N, M, answer, front, mid, back;
int blue[100001]; // 강의 길이 목록

bool b_search(int mid){ // mid 크기의 M장 블루레이에 모두 담기는지 확인.

  int sum_time = 0, cnt = 1; // sum_time 은 mid 이하여야 한다. 블루레이 개수 cnt.

  for(int i = N-1; i>=0; i--){

    if(blue[i] > mid){
      return false; // 블루레이 1장에 강의 1개도 못들어가는 경우.
    }

    sum_time += blue[i];
    if(sum_time > mid){
      cnt++;
      sum_time = blue[i];
    }
  }
  return M >= cnt; // 블루레이 개수가 M이하라면 만족.
}

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

  cin >> N >> M;
  for(int i = 0; i < N; i++) {
    cin >> blue[i];
    back += blue[i]; // 모든 강의 길이를 더해서 back에 저장 
  }
  front = 1; // 1분

  while(front <= back){

    mid = (front + back) / 2; // 블루레이 1장의 크기 mid

    if(b_search(mid)){ // mid크기의 블루레이로 M장 이하에 담을 수 있는지?
      answer = mid;
      back = mid-1;
    }else{
      front = mid+1;
    }
  }
  cout << answer;
  return 0;
}

수열 2559번 문제링크 

연속된 k개의 합을 구하되, 최대 합을 답으로 내는 문제다.

항상 k개여야 하니까, 시작 인덱스 0, 끝 인덱스 k-1 의 합으로 시작한다.

길이가 일정한 누적합이기 때문에, 시작 인덱스와 끝 인덱스만 바뀐다. 투포인터 문제다. 

k= 3 이라면,  아래 처럼 인덱스가 일정하게 증가한다. 

시작0 ~ 끝2,  시작1 ~ 끝3, 시작2 ~ 끝4

현재 시작인덱스의 값을 빼주고, 현재 끝인덱스 +1 의 값을 더해주면 된다. 

"맞았습니다"코드 링크 

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

int n, k, start_idx, end_idx;
long long sum, sum_temp;

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

  cin >> n >> k;
  vector<int> v(n); 
  for(int i = 0; i < n; i++) cin >> v[i]; // 입력받기 끝 

  // 인덱스 0부터 k-1까지 k개의 합 
  for(int i = 0; i < k; i++) sum_temp += v[i];
  start_idx = 0, end_idx = k-1; 

  sum = sum_temp;
  
  while(end_idx < n){ 
    sum_temp -= v[start_idx++]; // 현재 인덱스 값 빼기, 인덱스 증가
    if(end_idx + 1 == n) break;
    sum_temp += v[++end_idx];   // 인덱스 증가시킨 후 그 인덱스 값 더하기
    sum = max(sum_temp, sum);
  }
  cout << sum;
  return 0;
}

문제링크

연속된 수들의 합을 구해야한다.

수열의 시작 인덱스 a와 마지막 인덱스 b 를 두고 합이 m이 나오면 개수를 세준다. 

인덱스 a와 b는 같을 수 있다. b는 수열 길이 n 직전까지 증가한다.

계속 다른 수열합을 확인해야 하니까 a와 b 인덱스는 계속 증가한다.

단, a가 b보다 큰 인덱스가 되면 안된다.  a <= b  여야 한다. 

누적 합 sum이 m보다 작다면, 수열의 마지막 인덱스 b를 증가시킨다. 

누적 합 sum이 m보다 크다면, 수열의 시작 인덱스 a를 증가시킨다. 

맞았습니다 코드 링크 

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

ll a, b, sum, n, m, answer;
int arr[10005];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m;
  for(int i = 0; i < n; i++ ) cin >> arr[i];

  sum = arr[a];
  while(b < n && a <= b){
    if(sum <= m){
      if(sum == m) answer++;
      sum += arr[++b];
    }else { // sum > m
      sum -= arr[a++];
      if(a > b){
        b = a;
        sum = arr[a];
      }
    }
  }
  cout << answer;
  return 0;
}

문제 링크 

문자열로 주어진 숫자배열을 숫자만 추출해서 deque에 넣어야 했다. 

숫자가 여러자리 수인 경우가 있다. 그래서 숫자인 문자를 이어붙이고, 특수문자가 나오면 숫자인 문자열을 stoi()로 정수로 바꿨다. 

함수를 순회할 때,

D 일 때도 그렇고 R일 때도 deque가 비어있는건지를 확인해야한다. 이것때문에 계속 틀렸었다. 

"맞았습니다" 코드 링크 

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

int t, n;
string func, arr;

void check(string f, int n, string arr){
  string answer = "";
  bool flag = true;
  bool reverse_flag = false;
  deque<int> dq;

  string st_digit = "";
  for(int i = 0; i < arr.length(); i++){
    if(isdigit(arr[i])){
      st_digit += arr[i];
    }else{
      if(!st_digit.empty()){
        dq.push_back(stoi(st_digit));
        st_digit = "";
      }
    }
  }

  for(auto o : f){
    if(o == 'R') reverse_flag = !reverse_flag;
    else {
      if(dq.empty()) { flag= false; cout << "error\n"; break; }
      if(reverse_flag)  dq.pop_back();
      else dq.pop_front();
    }
  }

  if(flag){ // error 아닌 경우에만 배열 출력 
    cout << "[";

    if(reverse_flag){ // 뒤집혀있다면,
      for(auto d = dq.rbegin(); d != dq.rend(); d++){
        if(d == dq.rend()-1) {
          cout << *d;
        }
        else { cout << *d << ","; }
      }
    }else{
      for(auto d = dq.begin(); d != dq.end(); d++){
        if(d == dq.end()-1) {
          cout << *d;
        }
        else { cout << *d << ","; }
      }
    }
    cout << "]\n";
  }
}

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

  cin >> t;
  while(t--){
    cin >> func >> n >> arr;
    check(func, n, arr);
  }
  return 0;
}

문제 링크 

게임판 1차원 배열 board 가 있다. 뱀이나 사다리가 있는 칸만 0이 아닌 값이 있다. 

뱀이나 사다리가 있는 칸은, 목적지 칸 인덱스를 저장하도록 했다.

42칸에 사다리가 있으면 50으로 이동할 때, board[42] = 50 이다. 

1의 위치에서 시작하고, 목적지는 100이다. 최소 이동횟수를 구하는 bfs로 푼 코드다. 

"맞았습니다" 코드 링크 

숨바꼭질 문제와 비슷하게 느껴졌다. 

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

int n, m, a, b;
int answer = 1e9;
int board[102]; // 게임판
bool visited[102]; // 방문 체크

int bfs(){
    queue<pair<int,int>> qu; // <현재위치, 주사위 던진 횟수>
    qu.push({1, 0});
    visited[1] = true;

    while(!qu.empty()){
      pair<int,int> p = qu.front();
      qu.pop();

      int cur = p.first;
      int cur_cnt = p.second;

      if(cur == 100) {  answer = min(answer, cur_cnt); break; }// 목적지 도착

      for(int i = 1; i <= 6; i++){ // 주사위
        int next_cur = cur + i;
        if(next_cur > 100 || visited[next_cur]) continue; // 방문했거나 범위 초과시 지나감
        visited[next_cur] = true;
        
        if(board[next_cur] == 0) qu.push({next_cur, cur_cnt + 1});
        else qu.push({board[next_cur], cur_cnt + 1});
      }
    }
    return answer;
}

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

  cin >> n >> m;
  for(int i = 0; i < n+m; i++){ // 사다리와 뱀 
    cin >> a >> b; board[a] = b;
  }
  cout << bfs();
  return 0;
}

문제 링크 

조합을 하나씩 써 보면 그 값이 파스칼의 삼각형과 똑같이 나오는 것이 보인다. 

nCm == n-1 C m-1  + n-1 C m 

       1C0, 1C1

   2C0, 2C1, 2C2

3C0, 3C1, 3C2, 3C3

0개를 고를때와 n개중에 n개를 전부 고를 때는 값이 항상 1이다. 

조합 계산할 때 숫자가 커지니까 string 끼리의 계산이 필요했다. 

일의 자리끼리 계산 하고,  10으로 나눈 나머지를 일의자리로 저장한다.

일의 자리 계산 결과를 나누기 10하면, 올림수가 발생했는지 판단할 수 있다. 

"맞았습니다" 코드 링크 

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

int n, m;
string dp[102][102];

string numAdd(string n1, string n2){
  string answer = "";
  int sum = 0;
  int len = max(n1.size(), n2.size());

  for(int i = 0; i < len || sum; i++){ // 일의 자리를 덧셈한다.
    if(n1.size() > i) sum += (n1[i] - '0');
    if(n2.size() > i) sum += (n2[i] - '0');
    answer += ((sum % 10) + '0');
    sum /= 10;
  }

  return answer;
}

string combination(int n, int m){
  if(n == m || m == 0) return "1";

  string &res = dp[n][m];
  if(res != "") return res;

  res = numAdd(combination(n-1, m-1), combination(n-1, m));
  return res;
}

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

  cin >> n >> m;
  string ans = combination(n, m);
  reverse(ans.begin(), ans.end());
  cout << ans;
  return 0;
}

문제 링크

반복문 1개로 푼 코드가 있다. 숫자 제한이 작아서 완전 제곱수를 찾아가며 개수를 셌다. 

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

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

int m, n, i = 1, cnt;
vector<int> v;

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

  cin >> m >> n;

  while(i * i <= n){
    if(i*i >= m) {
      cnt++; v.push_back(i*i);
    }
    i++;
  }
  if(v.size()==0) cout << -1;
  else cout << accumulate(v.begin(), v.end(), 0) << '\n' << v[0];

  return 0;
}

두 번째는 완전 제곱수를 미리 찾아두고 시작한 코드다. 

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

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

int m, n, total_sum;
int minnum= 1e9;
int arr[100001];

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

  cin >> m >> n;
  int num = 1;
  while(num * num <= n){
    arr[num * num] = 1;
    num++;
  }

  for(int i = m; i <= n; i++){
    if(arr[i]) {
      total_sum += i;
      minnum = min(minnum, i);
    }
  }
  if(total_sum == 0) cout << -1;
  else cout << total_sum << '\n' << minnum;

  return 0;
}