BOJ 25304 : 영수증 (Bronze 4)

x = int(input())
n = int(input())
for _ in range(n):
    a, b = map(int, input().split())
    x -= a * b
print('Yes' if x == 0 else 'No')

BOJ 25314 : 코딩은 체육과목 입니다 (Bronze 5)

print('long '*(int(input())//4)+'int')

• 이로써 3단계 ‘반복문’을 뿌수는 데 성공했다.

BOJ 10810 : 공 넣기 (Bronze 3)

n, m = map(int, input().split())
arr = [0] * (n + 1)
for _ in range(m):
    i, j, k = map(int, input().split())
    for l in range(i, j+1):
        arr[l] = k
for i in range(1, n+1):
    print(arr[i], end=' ')

BOJ 10813 : 공 바꾸기 (Bronze 2)

n, m = map(int, input().split())
arr = list(range(n+1))
for _ in range(m):
    i, j = map(int, input().split())
    arr[i], arr[j] = arr[j], arr[i]
for i in range(1, n+1):
    print(arr[i], end=' ')

BOJ 10811 : 바구니 뒤집기 (Bronze 2)

n, m = map(int, input().split())
arr = list(range(n+1))
for _ in range(m):
    i, j = map(int, input().split())
    arr[i:j+1] = reversed(arr[i:j+1])
for i in range(1, n+1):
    print(arr[i], end=' ')

• 이로써 4단계 ‘1차원 배열’을 뿌수는 데 성공했다.

BOJ 25206 : 너의 평점은 (Silver 5)

s = 0
l = ['F', 'X', 'D0', 'D+', 'C0', 'C+', 'B0', 'B+', 'A0', 'A+']
n = 0
for i in range(20):
    a, b, c = input().split()
    if c == 'P':
        continue
    n += float(b)
    s += float(b) * l.index(c) / 2
print(s / n)

• 이로써 6단계 ‘심화 1’을 뿌수는 데 성공했다.
• 앞부분 너무 시시해서 못 풀겠다... 뒤로 좀 넘어가자.

BOJ 1520 : 내리막길 (Gold 3)

• 위상정렬로 DP 순서를 맞춰놓고 DP를 돌렸다.
• 그러나 굳이 in-degree을 구해서 비교하지 않아도 높이로 비교를 하면 되기에 priority_queue를 사용하면 되었다.

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

using pi = pair<int, int>;

int m, n;
int h[500][500];
int dp[500][500];
vector<pi> topo;
bool visited[500][500] = {false, };
const int D[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
map<pi, vector<pi>> G;

void dfs(int i, int j) {
  if (visited[i][j]) return;
  visited[i][j] = true;

  for (auto [di, dj] : D) {
    if (i+di>=0 && i+di<m && j+dj>=0 && j+dj<n && h[i][j] > h[i+di][j+dj]) {
      G[{i, j}].emplace_back(i+di, j+dj);
      dfs(i+di, j+dj);
    }
  }
  topo.insert(topo.begin(), {i, j});
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

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

  dfs(0, 0);

  dp[0][0] = 1;
  for (auto [i, j] : topo)
    for (auto [k, l] : G[{i, j}])
      dp[k][l] += dp[i][j];

  cout << dp[m-1][n-1];

  return 0;
}

BOJ 9466 : 텀 프로젝트 (Gold 3)

• 사이클을 찾아야 한다!
• out-degree가 1이므로, 각 요소_component에는 최대 1개의 사이클을 가질 수 있음을 알 수 있다.
• 그러니까 어느 노드를 기준으로 DFS를 돌리던 간에, 항상 사이클을 찾을 수 밖에 없다.
• 사이클에 포함된 노드를 찾는 것이 빡셀 수 있는데 사이클을 거꾸로 돌아오면서 처음 사이클을 마주친 노드에 되돌아 왔을 때까지의 노드들을 조사하면 된다.
  • 처음에는 스택을 따로 만들어야 하나 싶었는데 함수 스택을 사용하면 되겠다 싶었다.
• 한 요소 내에 부분적으로 노드를 방문하는 경우가 있지만, 같은 요소의 재방문을 피해야 한다. 이 점만 유의해서 코드를 작성하면 된다.

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

using vi = vector<int>;

int dfs(vi &G, vector<bool> &visited, vi &okay, int u) {
  visited[u] = true;

  int v = G[u];
  if (okay[v] != 0) { // already checked
    okay[u] = -1;
    return -1;
  }
  if (visited[v]) {
    okay[u] = 1;
    return u == v ? -1 : v;
  }
  int d = dfs(G, visited, okay, v);
  if (d != -1) {
    okay[u] = 1;
    return d == u ? -1 : d;
  }
  okay[u] = -1;
  return -1;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int T; cin >> T;
  while (T--) {
    int n; cin >> n;
    vi G(n+1);
    vector<bool> visited(n+1, false);
    vi okay(n+1, 0); // 0 : unknown, 1 : okay, -1 : not okay
    for (int u=1;u<=n;u++) {
      int v; cin >> v;
      G[u] = v;
    }
    for (int u=1;u<=n;u++) {
      if (!visited[u]) {
        dfs(G, visited, okay, u);
      }
    }
    int ans = 0;
    for (int u=1;u<=n;u++)
      ans += okay[u] != 1;
    cout << ans << '\n';
  }

  return 0;
}

BOJ 2623 : 음악프로그램 (Gold 3)

• 그냥 위상정렬 해주면 된다고 생각했다.
• 근데 사이클 검사해주는 게 생각보다 빡셌다.
• 모든 edge에 대해 위상정렬 순서(tout)와 반대되는 게 있으면 사이클이 있다고 판단했다.

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

using vi = vector<int>;
using vb = vector<bool>;
using pi = pair<int, int>;

vi topo;
vector<vi> G;
vb visited;
vi tout;
int timer = 0;
void dfs(int u) {
  if (visited[u]) return;
  visited[u] = true;

  for (int v : G[u]) {
    dfs(v);
  }
  topo.insert(topo.begin(), u);
  tout[u] = min(tout[u], timer++);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  G.resize(n+1);
  vector<pi> E;
  visited.resize(n+1,false);
  tout.resize(n+1, 1'000'000);
  for (int i=0;i<m;i++) {
    int k; cin >> k;
    int prev = -1;
    for (int j=0;j<k;j++) {
      int u; cin >> u;
      if (prev != -1) {
        G[prev].push_back(u);
        E.emplace_back(prev, u);
      }
      prev = u;
    }
  }

  for (int u=1;u<=n;u++)
    dfs(u);

  for (auto [u, v] : E) {
    if (tout[u] < tout[v]) {
      cout << 0;
      return 0;
    }
  }

  for (int u : topo)
    cout << u << '\n';

  return 0;
}

BOJ 1647 : 도시 분할 계획 (Gold 4)

• 크루스칼 알고리즘인데 가중치 하위 개만 고르면 된다는 사실을 쉽게 알 수 있다.
• 그냥 Disjoint Set으로 구현하려고 했는데, rank를 추가해주어야 TLE 없이 해결할 수 있다.

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

using vi = vector<int>;

struct DisjointSet {
  vi parent, rank;

  DisjointSet(int n) {
    parent.resize(n+1);
    rank.resize(n+1,1);
    for (int i=0;i<=n;i++)
      parent[i]=i;
  }

  int find(int x) {
    if (parent[x] == x) return x;
    return find(parent[x]);
  }

  void merge(int x, int y) {
    x=find(x), y=find(y);
    if (rank[x]>rank[y]) swap(x,y);
    parent[x]=y;
    rank[y]+=rank[x];
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  vector<tuple<int, int, int>> edges(m);
  for (int i=0;i<m;i++) {
    int a, b, c; cin >> a >> b >> c;
    edges[i] = {c, a, b};
  }
  sort(edges.begin(), edges.end());
  DisjointSet ds(n);
  int cnt=0, i=0, sum=0;
  while (cnt<n-2) {
    auto [c, a, b] = edges[i];
    if (ds.find(a) != ds.find(b)) {
      ds.merge(a, b);
      cnt++;
      sum += c;
    }
    i++;
  }
  cout << sum;

  return 0;
}

BOJ 9527 : 1의 개수 (Gold 2)

• 다음 수열을 함께 보자.

• ()번째 자리수의 합을 유심히 살펴보면 다음 식이 떠오른다. (일종의 더블 카운팅이다.)

  • 여기서 는 번째 자리수를 갖는 이하의 자연수의 개수를 의미한다.

• 위의 발견대로 구현하면 된다.

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

using ll = long long;

ll sum_f(ll a) {
  ll d=1, res=0;
  while (a>0) {
    res+=a/(2*d)*d+min(a%(2*d),d);
    a-=d;
    d<<=1;
  }
  return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  ll a, b; cin >> a >> b;
  cout << sum_f(b) - sum_f(a-1);

  return 0;
}

BOJ 1202 : 보석 도둑 (Gold 2)

• 작은 가방부터 그 가방이 넣을 수 있는 보석들 중 가장 비싼 보석을 넣어주면 된다. 다음 그림을 참고하자.

  

• Binary Search Tree를 위해 multiset을 사용하면 된다. 처음에 set을 사용했다가 왜 틀렸는지 한참 해맸다.

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

using ll = long long;
using vi = vector<int>;
using vb = vector<bool>;
using pi = pair<int, int>;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, k; cin >> n >> k;
  vector<pi> MV(n);
  for (int i=0;i<n;i++) {
    int m, v; cin >> m >> v;
    MV[i] = {m, v};
  }
  sort(MV.begin(), MV.end());

  vi C(k);
  for (int i=0;i<k;i++)
    cin >> C[i];
  sort(C.begin(), C.end());

  multiset<pi, greater<>> s;
  int idx=0;
  ll ans=0;
  for (auto c : C) {
    for (;idx<n && MV[idx].first<=c;idx++) {
      auto [m, v] = MV[idx];
      s.insert({v, m});
    }
    if (s.empty()) continue;
    ans += (*s.begin()).first;
    s.erase(s.begin());
  }
  cout << ans;

  return 0;
}

• 이로써 solved.ac CLASS 5를 취득했다.

BOJ 1918 : 후위 표기식 (Gold 2)

• AST를 만들고 post-order로 순회하면 된다.

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

using vi = vector<int>;

struct Node {
  Node *left=nullptr, *right=nullptr;
  char val='\0'; // +-*/ or A-Z
  int start=-1, end=-1;
};

vector<Node*> nodes;

Node* ast(string const& s, int start, int end) { // [start, end]
  vector<Node> operands;
  vi operators;
  int paren_idx=-1;
  int paren_cnt=0;
  for (int i=start;i<=end;i++) {
    char ch=s[i];
    if (paren_cnt>0) {
      if (ch=='(') {
        paren_cnt++;
      } else if (ch==')') { // ch==')' -> paren_idx>0. otherwise, bad expression
        paren_cnt--;
        if (paren_cnt == 0) {
          operands.push_back({.start=paren_idx+1, .end=i-1});
        }
      }
      continue;
    }
    if (ch=='(') {
      paren_cnt++;
      paren_idx = i;
    } else if (ch=='+'||ch=='-'||ch=='*'||ch=='/') {
      operators.push_back(i);
    } else { // alphabet
      operands.push_back({.val=ch, .start=i, .end=i});
    }
  }
  // mul, div -> node
  for (int i=0;i<operators.size();i++) {
    if (s[operators[i]]=='*'||s[operators[i]]=='/') {
      Node *left, *right;
      if (operands[i].val == '\0') {
        left = ast(s, operands[i].start, operands[i].end);
      } else {
        left = new Node;
        *left = operands[i];
        nodes.push_back(left);
      }
      if (operands[i+1].val == '\0') {
        right = ast(s, operands[i+1].start, operands[i+1].end);
      } else {
        right = new Node;
        *right = operands[i+1];
        nodes.push_back(right);
      }
      operands.erase(operands.begin()+i, operands.begin()+i+2);
      operands.insert(operands.begin()+i, {.left=left, .right=right, .val=s[operators[i]]});
      operators.erase(operators.begin()+i);
      i--;
    }
  }
  if (operators.empty()) {
    if (operands[0].val == '\0')
      return ast(s, operands[0].start, operands[0].end);

    Node *root = new Node;
    *root = operands[0];
    nodes.push_back(root);
    return root;
  }
  Node *root;
  for (int i=0;i<operators.size();i++) {
    if (i == 0) {
      Node *left, *right;
      root = new Node;
      if (operands[i].val == '\0') {
        left = ast(s, operands[i].start, operands[i].end);
      } else {
        left = new Node;
        *left = operands[i];
        nodes.push_back(left);
      }
      if (operands[i+1].val == '\0') {
        right = ast(s, operands[i+1].start, operands[i+1].end);
      } else {
        right = new Node;
        *right = operands[i+1];
        nodes.push_back(right);
      }
      root->val = s[operators[i]];
      root->left = left;
      root->right = right;
    } else {
      Node *new_root = new Node, *right;
      if (operands[i+1].val == '\0') {
        right = ast(s, operands[i+1].start, operands[i+1].end);
      } else {
        right = new Node;
        *right = operands[i+1];
        nodes.push_back(right);
      }
      new_root->val = s[operators[i]];
      new_root->left = root;
      new_root->right = right;
      root = new_root;
      nodes.push_back(new_root);
    }
  }
  return root;
}

void dfs(Node *node) {
  if (node->left) dfs(node->left);
  if (node->right) dfs(node->right);
  if (node->val) cout << node->val;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  string s; cin >> s;
  Node *root = ast(s, 0, s.length()-1);

  dfs(root);

  for (Node *n : nodes)
    delete n;

  return 0;
}

• 너무 어렵게 풀었다. 모노톤 스택으로 해결 가능하다.

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

int prec(char op) {
  if (op=='+'||op=='-') return 1;
  if (op=='*'||op=='/') return 2;
  return 0;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  string s; cin >> s;
  stack<char> ops;

  for (char ch : s) {
    if (isalpha(ch)) {
      cout << ch;
    } else if (ch=='(') {
      ops.push(ch);
    } else if (ch==')') {
      while (!ops.empty() && ops.top() != '(')
        cout << ops.top(), ops.pop();
      if (!ops.empty()) ops.pop(); // remove '('
    } else {
      while (!ops.empty() && prec(ops.top()) >= prec(ch))
        cout << ops.top(), ops.pop();
      ops.push(ch);
    }
  }

  while (!ops.empty())
    cout << ops.top(), ops.pop();

  return 0;
}

• 이 문제로 티어 플래티넘 5를 얻었다.