250216

BOJ 1105 : 팔 (Silver 1)

처음에는 나이브하게 부터 까지 돌 생각을 했지만 범위가 너무 넓어서 이건 아니겠다는 생각을 함.
이후에는 예시를 보고 과 의 자리수가 같을 때 leading 8의 최솟값인가 생각을 함.
그러다 , 의 반례를 떠올리고 이것이 아님을 깨달음.
직관적으로 과 의 common prefix에서의 8의 개수라고 추측을 함.
common prefix가 아닌 부분을 8이 아니도록 바꿈으로써 8의 개수를 최소화할 수 있을 것이라고 간단하게 논증을 세우고 코드를 짬.

l, r = input().split()

if len(l) < len(r):
    print(0)
else:
    eight = 0
    for i in range(len(l)):
        if l[i] != r[i]:
            break
        if l[i] == '8':
            eight += 1
    print(eight)

BOJ 1141 : 접두사 (Silver 1)

이 50이하로 작길래 조금 너그럽게 생각해도 되겠다고 생각했다.
첫번째 접근
- 처음에 으로 시작해서 일 때, 를 하나씩 깎는 것으로 결과를 계산할 수 있을 것으로 예상했다.
- 하지만 에서 최적해가 2이므로 에서 깎았으면 가 아닌 문자열에 대해서는 더 이상 세지 않으면 될 것 같았다.
- 예제 중 같은 단어가 두 번 등장할 때 문제가 발생하길래 pairwise하게 중복해서 세어지는 것을 제거했다.
```
n = int(input())
s = []
for i in range(n):
    s.append(input())

cnt = n
same = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        if s[j].startswith(s[i]):
            cnt -= 1
            if s[i] == s[j]:
                same += 1
            break

cnt += same // 2
print(cnt)
```
그러나 이는 올바른 방식이 아니었다. 결국 여기서 내재하는 구조는 ¹로 이어지는 트리 구조인데 이 트리의 leaf의 개수를 세는 것이 문제의 답인 것이다. leaf의 개수는 첫번째 접근에서처럼 전체 노드 수에서 하나씩 빼서는 구하기 어렵다.

두번째 접근

위에서 말한 대로 짜면 된다. 동일한 단어는 최대 1개만 들어갈 수 있으므로 처음부터 중복 제거를 해준다. 으로 해결할 수 있다.

n = int(input())
s = []
for i in range(n):
    s.append(input())

s = list(set(s))
n = len(s)

l = [True] * n

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        if s[j].startswith(s[i]):
            l[i] = False

print(sum(l))

BOJ 6549 : 히스토그램에서 가장 큰 직사각형 (Platinum 5)

정말 많이, 그리고 오랫동안 (진짜 몇달간) 고민했던 문제다.
아무리 생각해도 방법 밖에 떠오르지 않아서 발상의 전환이 필요했다.
의 범위가 너무 커서 를 기준으로 짜르면 안되지 않나 하고 일찌감치 버려두었다. 하지만, 오늘 좌표 압축 하면 되지 않을까 싶었다.
를 높이가 큰 순으로 정렬하고 각 과 인접하는 것을 찾아서 Union-Find의 merge 연산을 해주면 된다고 생각했다.
원래는 높이를 map<int,vector<int>> 식으로 저장하는 게 낫지 않을까 싶었는데, 구현도 불편하고 그냥 해도 풀릴 것 같았다.
아무튼 풀고 나서 기분이 매우 좋았다.

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

typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;

struct UnionFind {
  vi parent;
  vi setSize;

  UnionFind(int n) {
    parent.resize(n, -1);
    setSize.resize(n, 0);
  }

  int getParent(int x) {
    if (parent[x] == -1) return -1;
    if (parent[x] == x) return x;
    return parent[x] = getParent(parent[x]);
  }

  // returns set size
  int merge(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if (a == -1 || b == -1) return 0;
    if (a < b)
      return parent[b] = a, setSize[a] += setSize[b]; // store size only in parent.
    return parent[a] = b, setSize[b] += setSize[a];
  }

  void addItem(int a) {
    parent[a] = a;
    setSize[a] = 1;
  }
};

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

  int n;
  while (cin >> n, n > 0) {
    vector<pii> hp(n);
    UnionFind uf(n);
    for (int i=0;i<n;i++) {
      int h;
      cin >> h;
      hp.emplace_back(h, i);
    }
    sort(hp.begin(), hp.end(), greater());

    ll mm = hp[0].first;
    for (auto [h, p] : hp) {
      uf.addItem(p);

      if (p + 1 < n)
        mm = max(mm, (ll) uf.merge(p, p + 1) * h);
      if (p - 1 >= 0)
        mm = max(mm, (ll) uf.merge(p, p - 1) * h);
    }

    cout << mm << '\n';
  }

  return 0;
}

BOJ 1011 : Fly me to the Alpha Centauri (Gold 5)

메모리를 512MB나 주길래 DP인가 싶었다.
근데 아무리 생각해봐도 DP로 할 수 있는게 없었다. 메모이제이션으로 하려고 했는데, 메모리 초과가 났다.
나열하다보니까 규칙이 보였다. 1 2 1, 1 2 2 1, 1 2 3 2 1 이런 식으로 길이 내에서 최대 합을 이루는 수열을 생각하고, 그 합보다 작거나 같은 최장 수열의 길이를 결과로 내놓으면 된다.
앞으로는 큰 메모리나 긴 실행 시간으로부터 힌트를 얻으려고 하지 말아야겠다.

n = int(input())
for i in range(n):
    a, b = map(int, input().split())
    x = b - a
    y = 0
    i = 1
    while True:
        y += (i + 1) // 2
        if y >= x:
            break
        i += 1

    print(i)

250217

BOJ 1189 : 컴백홈 (Silver 1)

, 가 매우 작아서 백트래킹하면 되겠다고 생각했다.
처음에 visited[r-1][0]를 true로 초기화해주는 것을 까먹었다.

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

int r, c, k;
bool visited[5][5];
char _map[5][6];

const int D[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int dfs(int i, int j, int cnt) {
  if (i == 0 && j == c-1)
    return cnt == k;

  int result = 0;
  for (auto [di, dj] : D) {
    if (i+di >= 0 && i+di < r && j+dj >= 0 && j+dj < c && _map[i+di][j+dj] == '.' && !visited[i+di][j+dj]) {
      visited[i+di][j+dj] = true;
      result += dfs(i+di, j+dj, cnt+1);
      visited[i+di][j+dj] = false;
    }
  }
  return result;
}

int main() {
  scanf("%d%d%d", &r, &c, &k);
  for (int i = 0; i < r; i++)
    scanf("%s", _map[i]);

  memset(visited, false, 25 * sizeof(bool));
  visited[r-1][0] = true;

  printf("%d", dfs(r - 1, 0, 1));
  return 0;
}

BOJ 2607 : 비슷한 단어 (Silver 2)

단어의 조성을 파악하고 각 조성의 차이가 1 이하이되, 1과 -1이 각각 최대 1번까지만 등장 가능하다는 것을 고려하여 구현하면 된다.
단어의 개수를 , 단어의 최대 길이를 이라 할 때, 시간 복잡도는 이다.

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

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

  int n; cin >> n;

  string s; cin >> s;

  int counter[28] = {0, };
  for (char ch : s)
    counter[ch-'A']++;

  int cnt = 0;
  for (int i=0;i<n-1;i++) {
    string s2; cin >> s2;

    int counter2[28] = {0, };
    for (char ch : s2)
      counter2[ch-'A']++;

    int minusOne = 0;
    int plusOne = 0;
    bool success = true;
    for (int j=0;j<28;j++) {
      int diff = counter[j] - counter2[j];
      if (diff < -1 || diff > 1) {
        success = false;
        break;
      }
      if (diff == -1) minusOne++;
      if (diff == 1) plusOne++;
    }
    if (success && minusOne <= 1 && plusOne <= 1) {
      cnt++;
    }
  }

  cout << cnt;

  return 0;
}

250218

BOJ 1992 : 쿼드트리 (Silver 1)

DFS로 쉽게 해결 가능하다.

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

string _map[64];

string dfs(int i, int j, int w) {
  if (w == 1) {
    return string(1, _map[i][j]);
  }

  string s1 = dfs(i, j, w/2);
  string s2 = dfs(i, j + w/2, w/2);
  string s3 = dfs(i + w/2, j, w/2);
  string s4 = dfs(i + w/2, j + w/2, w/2);

  if (s1[0] != '(' && s1[0] == s2[0] && s2[0] == s3[0] && s3[0] == s4[0]) {
    return s1;
  }
  return "(" + s1 + s2 + s3 + s4 + ")";
}

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

  int n;
  cin >> n;

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

  cout << dfs(0, 0, n);

  return 0;
}

BOJ 7562 : 나이트의 이동 (Silver 1)

BFS로 쉽게 해결 가능하다.

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

const int D[8][2] = {{1, 2}, {2, 1}, {1, -2}, {2, -1}, {-1, -2}, {-2, -1}, {-1, 2}, {-2, 1}};

struct Node {
  int i;
  int j;
  int c;
};

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

  int t; cin >> t;

  while (t--) {
    int l; cin >> l;
    bool visited[l][l];
    memset(visited, false, l * l * sizeof(bool));
    int sx, sy; cin >> sx >> sy;
    int tx, ty; cin >> tx >> ty;

    queue<Node> q;
    q.push(Node { sx, sy, 0 });
    visited[sx][sy] = true;

    while (!q.empty()) {
      auto [i, j, c] = q.front();
      q.pop();

      if (i == tx && j == ty) {
        cout << c << '\n';
        break;
      }

      for (auto [di, dj] : D) {
        if (i+di>=0 && i+di<l && j+dj>=0 && j+dj<l && !visited[i+di][j+dj]) {
          visited[i+di][j+dj] = true;
          q.push(Node { i+di, j+dj, c+1 });
        }
      }
    }
  }

  return 0;
}

BOJ 1850 : 최대공약수 (Silver 1)

푸는데 좀 시간이 걸렸다.
1로만 구성된 두 블록이 있다고 할 때, 작은 블록을 등분한 조각을 작은 블록에 이어붙여 큰 블록을 만들 수 있을까를 고민하여 접근하였다.
접근한 대로 맞긴 했지만 증명하는 게 어려워서 포기했다.
GPT가 알려준 증명을 첨부하겠다.

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

typedef long long ll;

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

  ll a, b; cin >> a >> b;

  for (ll i=0;i<gcd(a, b);i++)
    cout << '1';

  return 0;
}

증명

먼저, , 를 양의 정수라고 하고, 라고 하자. 우리가 증명할 식은

인데, 우선 분자에 대해 아래의 사실을 증명하자.

이 과 의 공약수임을 보임

이므로, 정수 이 존재하여

라고 할 수 있다.

이때,

이므로, 은 의 인수이다. 같은 논리로 은 의 인수이다.

따라서, 이고 이다.

이 최대공약수임을 보임

반대로, 이 과 의 임의의 공약수라고 하자. 그러면

이다.

Bézout의 정리에 의해, 는 와 의 정수 선형 결합으로 나타낼 수 있으므로, 즉 가 존재하여

양변에 의 거듭제곱을 취하면

따라서,

즉, 은 과 의 모든 공약수를 나누므로,

최종 결론

문제에서 주어진 두 수는 와 이다. 과 는 모두 의 배수이므로, 양변을 로 나누어도 최대공약수의 관계는 보존된다. 즉,

이로써

임을 증명하였다.

BOJ 11403 : 경로 찾기 (Silver 1)

Transitive Closure 구하는 문제이다.
처음에 반복문 순서를 헷갈렸는데, DP적 관점으로 생각할 때 로 갈 수 있는 다리가 중에 있는지를 점진적으로 확인해야 하기에 중간 다리인 를 맨 나중에 놓는 것이다.

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

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

  int n; cin >> n;

  bool mat[100][100];
  for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
      cin >> mat[i][j];

  for (int k=0;k<n;k++)
    for (int i=0;i<n;i++)
      for (int j=0;j<n;j++)
        mat[i][j] = mat[i][j] || (mat[i][k] && mat[k][j]);

  for (int i=0;i<n;i++) {
    for (int j=0;j<n;j++) {
      cout << mat[i][j] << ' ';
    }
    cout << '\n';
  }

  return 0;
}

BOJ 2583 : 영역 구하기 (Silver 1)

DFS로 풀면 된다.
좌표가 제법 헷갈린다.

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

typedef long long ll;

bool visited[100][100] = {false, };
bool mat[100][100] = {false, };

const int D[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int m, n;

int dfs(int x, int y) {
  visited[y][x] = true;
  int result = 1;
  for (auto [dx, dy] : D) {
    if (x+dx>=0 && x+dx<n && y+dy>=0 && y+dy<m && !visited[y+dy][x+dx] && !mat[y+dy][x+dx]) {
      result += dfs(x+dx, y+dy);
    }
  }
  return result;
}

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

  int k;
  cin >> m >> n >> k;
  for (int t=0;t<k;t++) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    for (int x=x1;x<x2;x++)
      for (int y=y1;y<y2;y++)
        mat[y][x] = true;
  }

  vector<int> results;
  for (int x=0;x<n;x++) {
    for (int y=0;y<m;y++) {
      if (!mat[y][x] && !visited[y][x]) {
        results.push_back(dfs(x, y));
      }
    }
  }

  sort(results.begin(), results.end());

  cout << results.size() << '\n';
  for (int result : results) {
    cout << result << ' ';
  }

  return 0;
}

BOJ 11057 : 오르막 수 (Silver 1)

각 자릿수를 ()이라 할 때, 다음을 만족하는 수의 개수를 찾는 문제이다.
각 자릿수의 조성(0이 몇 개고, 1이 몇 개고, ...)만 결정하면 오르막수가 이것을 정렬한 것으로 유일하게 결정되므로 조성의 경우의 수를 찾으면 된다. 길이가 인 수에서 숫자 의 개수를 ()라고 할 때, 다음의 경우의 수를 세면 된다.
중복조합으로 계산하면 이다.
중복조합을 그냥 재귀로 계산하면 이므로 상당히 문제가 있다. 2D 메모이제이션을 활용하도록 하자. 으로 해결 가능하다.

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

const int MOD = 10007;

int memo[1010][1010] = {0, };

int comb(int n, int r) {
  if (n == r || r == 0) return 1;
  if (memo[n][r] > 0) return memo[n][r];
  return memo[n][r] = comb(n-1,r-1) % MOD + comb(n-1,r) % MOD;
}

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

  int n; cin >> n;
  cout << (comb(n+9, 9) % MOD);

  return 0;
}

BOJ 2688 : 줄어들지 않아 (Silver 1)

바로 윗 문제랑 비슷하다고 해서 날먹했다. 이러면 안 되려나...

BOJ 1926 : 그림 (Silver 1)

또 DFS 문제다. 2583이랑 매우 비슷하다. 날먹 죄송

BOJ 11404 : 플로이드 (Gold 4)

플로이드-워셜 알고리즘이다.

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

const int INF = 100000000;

int main() {
  int n, m; cin >> n >> m;
  int mat[100][100] = {0, };

  for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
      mat[i][j] = INF;

  for (int i=0;i<m;i++) {
    int a, b, c;
    cin >> a >> b >> c;
    mat[a-1][b-1] = min(mat[a-1][b-1], c);
  }

  for (int k=0;k<n;k++)
    for (int i=0;i<n;i++)
      for (int j=0;j<n;j++)
        mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);

  for (int i=0;i<n;i++) {
    for (int j=0;j<n;j++) {
      cout << (mat[i][j] >= INF || i == j ? 0 : mat[i][j]) << ' ';
    }
    cout << '\n';
  }

  return 0;
}

250219

BOJ 5014 : 스타트링크 (Silver 1)

흔치 않은 1D BFS이다.
더 효율적인 방법이 있을 듯 하다.

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

typedef pair<int, int> pii;

int main() {
  int f, s, g, u, d;
  cin >> f >> s >> g >> u >> d;

  queue<pii> q;
  q.emplace(s, 0);
  bool visited[1000001] = {false, };

  int result = -1;
  while (!q.empty()) {
    auto [p, c] = q.front();
    q.pop();

    if (p == g) {
      result = c;
      break;
    }

    if (p+u<=f && !visited[p+u]) {
      q.emplace(p+u, c+1);
      visited[p+u] = true;
    }

    if (p-d>=1 && !visited[p-d]) {
      q.emplace(p-d, c+1);
      visited[p-d] = true;
    }
  }

  if (result == -1) {
    cout << "use the stairs";
  } else {
    cout << result;
  }

  return 0;
}

BOJ 1759 : 암호 만들기 (Gold 5)

백트래킹 문제다.
STL string이 익숙하지 않아서 애 좀 먹었다.

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

int l, c;
vector<char> alphabet;

bool isCon(char ch) {
  switch (ch) {
    case 'a':
    case 'e':
    case 'i':
    case 'o':
    case 'u':
      return false;
    default:
      return true;
  }
}

string s;
void dfs(int len, int alphaIdx, int conCnt) {
  if (len == l) {
    if (conCnt >= 2 && l - conCnt >= 1) {
      cout << s << '\n';
    }
    return;
  }

  for (int i = alphaIdx + 1; i < c; i++) {
    s.push_back(alphabet[i]);
    dfs(len + 1, i, conCnt + isCon(alphabet[i]));
    s.pop_back();
  }
}

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

  cin >> l >> c;
  alphabet.resize(c);

  for (int i=0;i<c;i++)
    cin >> alphabet[i];

  sort(alphabet.begin(), alphabet.end());

  for (int i=0; i<c-l+1; i++) {
    s = string(1, alphabet[i]);
    dfs(1, i, isCon(alphabet[i]));
  }

  return 0;
}

BOJ 1025 : 제곱수 찾기 (Gold 5)

, 의 범위가 크지 않아서 으로 해결할 수 있다.
모든 방향 구하는 게 개빡세다...

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

bool isSquare(int n) {
  int rt = (int) sqrt(n);
  return rt * rt == n;
}

int toNum(char ch) {
  return ch - '0';
}

const int P[4][2] = {{1, 1}, {-1, 1}, {-1, -1}, {1, -1}};

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

  int n, m;
  char table[9][10];

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

  int mm = -1;
  for (int i=0;i<n;i++) {
    for (int j=0;j<m;j++) {
      if (isSquare(toNum(table[i][j]))) {
        mm = max(mm, toNum(table[i][j]));
      }
      for (int di=0;di<n;di++) {
        for (int dj=0;dj<m;dj++) {
          if (di == 0 && dj == 0) continue;
          for (auto [pi, pj] : P) {
            int s = 0;
            for (int k=0;i+di*k*pi>=0 && i+di*k*pi<n && j+dj*k*pj>=0 && j+dj*k*pj<m; k++) {
              s = s * 10 + toNum(table[i+di*k*pi][j+dj*k*pj]);
              if (isSquare(s))
                mm = max(mm, s);
            }
          }
        }
      }
    }
  }

  cout << mm;

  return 0;
}

BOJ 1654 : 랜선 자르기 (Silver 2)

주어진 랜선으로 만들 수 있는 길이 의 랜선의 개수를 이라 하자.
랜선의 길이를 1만큼 증가시켰을 떄, 개수는 항상 같거나 줄어드므로 은 단조감소한다.
따라서 분할정복(=이진 탐색)으로 인 upper bound를 에 찾을 수 있다.
마지막에 오버플로우 때문에 미치는 줄 알았다.

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

typedef vector<int> vi;
typedef long long ll;

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

  int k, n; cin >> k >> n;
  vi len(k);
  int mm = 0;

  for (int i=0; i<k; i++)
    cin >> len[i], mm = max(mm, len[i]);

  int l = 1, r = mm;
  while (l < r) {
    int mid = ((ll) l + r + 1) / 2;

    ll cnt = 0;
    for (int i=0; i<k; i++)
      cnt += len[i] / mid;

    if (cnt >= n) l = mid;
    else r = mid - 1;
  }

  cout << l;

  return 0;
}

분할정복 짜는 거 진짜 너무 헷갈린다. 한 번 정리하고 넘어가자.

팁분할정복 헷갈리지 않기

lower bound를 기본 틀로 잡자.

int lower_bound(vector<int>& A, int k) {
  int lo = 0, hi = A.size(); // [lo, hi)
  while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (A[mid] >= k) // mid가 정답(>=target)이 될 수 있으니 hi를 mid로 옮긴다.
      hi = mid;
    else
      lo = mid + 1;
  }
  return lo;
}

이제 upper bound는 저 부등호에서 등호를 빼면 되는 것이다! upper bound를 인 의 lower bound로 해석하는 것이 되겠다.

int upper_bound(vector<int>& A, int k) {
  int lo = 0, hi = A.size(); // [lo, hi)
  while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (A[mid] > k) // mid가 정답(>target)이 될 수 있으니 hi를 mid로 옮긴다.
      hi = mid;
    else
      lo = mid + 1;
  }
  return lo - 1;
}

왜 반열린구간 으로 만들었나?
- 닫힌구간으로 만들 때에는 while문의 조건이 lo <= hi가 되고², 이 경우 일 경우에만 반복문을 빠져나가니까 이 경우 와 중 어느 것이 정답인지 알 수 없기 때문이다. 굳이 그러려면 따로 변수를 만들어서 정답을 미리 저장해두어야 한다.
- 반열린구간으로 만들면 그냥 나 중에 아무거나 고르면 된다.
왜 굳이 mid = (hi + lo) / 2 대신 mid = lo + (hi - lo) / 2로 구현했나?
- 둘은 수학적으로는 동일한 구문이다. 다만, 오버플로우를 방지하기 위해선 후자가 나은 구현이다.

BOJ 1541 : 잃어버린 괄호 (Silver 2)

Matrix Chain Multiplication Problem이 떠올랐다. 그래서 2D DP로 짰다.

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

typedef vector<int> vi;

const int INF = numeric_limits<int>::max();

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

  string s; cin >> s;

  vi nums;
  vector<char> ops;
  int dp[25][25];

  int num = 0;
  for (char ch : s) {
    if (ch >= '0' && ch <= '9') {
      num = num * 10 + (ch - '0');
    } else {
      nums.push_back(num);
      ops.push_back(ch);
      num = 0;
    }
  }
  nums.push_back(num);

  int n = nums.size();
  for (int i=0; i<n; i++) {
    dp[i][i] = nums[i];
    for (int j=i+1; j<n; j++)
      dp[i][j] = INF;
  }

  for (int w=2; w<=n; w++) {
    for (int i=0; i<n-w+1; i++) {
      for (int k=0; k<w-1; k++) {
        dp[i][i+w-1] = min(dp[i][i+w-1],
                             ops[i+k] == '+' ? dp[i][i+k] + dp[i+k+1][i+w-1] : dp[i][i+k] - dp[i+k+1][i+w-1]);
      }
    }
  }

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

  return 0;
}

그러나... 솔브드 기여 창을 보고 깜짝 놀라고 말았다... 그리디로 풀 수 있다는 것을...
- 대충 -가 나오면 다음 +가 등장하기 전까지 모든 수를 음수로 만들어 버릴 수 있으니 첫 - 이후 모든 +를 -로 만들어서 계산하면 되는 것이다..
- 2D DP로 짜면서, 아니... 이렇게 어렵다고?? 실버 2가??를 되뇌며 풀었다.

250221

BOJ 15868 : 치킨 배달 (Gold 5)

, 의 크기가 크지 않아서 모든 경우를 다 해보면 되겠다고 생각했다.
치킨집을 최대 개를 선택하라고 했지만, 개 택하는 것보다 개 택하는 것이 무조건 작거나 같게 되므로 개를 선택하는 경우만 고려하면 된다.
next_permutation을 이용하여 구현하였다.

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

typedef pair<int, int> pii;

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

  int n, m;
  cin >> n >> m;

  vector<pii> h;
  vector<pii> c;

  for (int i=0;i<n;i++)
    for (int j=0;j<n;j++) {
      int x; cin >> x;
      if (x == 1)
        h.emplace_back(i, j);
      else if (x == 2)
        c.emplace_back(i, j);
    }

  vector<int> ind(c.size(), 0);
  for (int i=c.size()-m;i<c.size();i++)
    ind[i]=1;

  int mm = numeric_limits<int>::max();
  do {
    int s = 0;
    for (auto [hi, hj] : h) {
      int mmm = numeric_limits<int>::max();
      for (int i=0;i<c.size();i++) {
        if (ind[i] == 1) {
          auto [ci, cj] = c[i];
          mmm = min(mmm, abs(ci - hi) + abs(cj - hj));
        }
      }
      s += mmm;
    }
    mm = min(mm, s);
  } while (next_permutation(ind.begin(), ind.end()));

  cout << mm;

  return 0;
}

BOJ 2504 : 괄호의 값 (Gold 5)

스택으로 풀면 된다.

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

struct Node {
  int type; // 0 : value, 1: (, 3: [
  int value;
};

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

  string s;
  cin >> s;

  stack<Node> stack;

  for (char ch : s) {
    if (ch == '(') {
      stack.push(Node { 1, 0 });
    } else if (ch == '[') {
      stack.push(Node { 3, 0 });
    } else {
      bool ok = false;
      int val = 0;
      while (!stack.empty()) {
        Node top = stack.top(); stack.pop();
        if (top.type == (ch == ')' ? 3 : 1))
          break;
        if (top.type == (ch == ')' ? 1 : 3)) {
          ok = true;
          break;
        }

        if (top.type == 0)
          val += top.value;
      }
      if (!ok) {
        cout << 0; return 0;
      }
      int m = ch == ')' ? 2 : 3;
      stack.push(Node { 0, val == 0 ? m : m * val});
    }
  }

  int val = 0;
  while (!stack.empty()) {
    Node top = stack.top(); stack.pop();
    if (top.type != 0) {
      cout << 0; return 0;
    }
    val += top.value;
  }
  cout << val;

  return 0;
}

BOJ 11054 : 가장 긴 바이토닉 부분 수열 (Gold 4)

11053번 문제와 거의 비슷하지만 증가 감소 여부를 구분해서 2D DP에 저장하면 된다.

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

int n;
int s[1000];
int dp[1000][2] = {0, };

int dfs(int i, bool turn) {
  if (i == n-1) return 1;

  if (dp[i][turn] == 0) {
    dp[i][turn] = 1;
    for (int j=i+1;j<n;j++) {
      if (s[i] < s[j] && !turn) {
        dp[i][turn] = max(dp[i][turn], 1 + dfs(j, false));
      } else if (s[i] > s[j]) {
        dp[i][turn] = max(dp[i][turn], 1 + dfs(j, true));
      }
    }
  }

  return dp[i][turn];
}

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

  cin >> n;

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

  int result = 0;
  for (int i=0;i<n;i++)
    result = max(result, dfs(i, false));

  cout << result;

  return 0;
}

BOJ 1038 : 감소하는 수 (Gold 5)

이 자리수일 조건은 이므로 을 찾고 해당 블록에서의 index를 구해서 next_permutation으로 블록에서 해당 index번째의 감소하는 수를 구하면 된다.
블록 index 구하는 게 너무 빡세서 진짜 한참동안 붙잡았었다.

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

typedef vector<int> vi;

int memo[11][11] = {0, };
int comb(int n, int r) {
  if (n == r || r == 0) return 1;
  if (memo[n][r] > 0) return memo[n][r];
  return memo[n][r] = comb(n-1, r) + comb(n-1, r-1);
}

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

  int n; cin >> n;
  n++;

  int m=1, s=0;
  bool okay = false;
  for (m=1;m<=10;m++) {
    int d = comb(10, m);
    if (s + 1 <= n && n <= s + d) {
      n -= s + 1;
      okay = true;
      break;
    }
    s += d;
  }
  if (!okay) {
    cout << -1;
    return 0;
  }

  vi ind(10, 0);
  for (int i=10-m; i<10; i++)
    ind[i] = 1;

  for (int i=0; i<n && next_permutation(ind.begin(), ind.end()); i++) {}

  for (int i=0;i<10;i++)
    if (ind[i])
      cout << (9-i);

  return 0;
}

BOJ 1041 : 주사위 (Gold 5)

잘 생각해보면 된다.

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

typedef long long ll;

const int TWO[12][2] = {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {1, 2}, {1, 3}, {1, 5}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}};
const int THREE[8][3] = {{0, 1, 2}, {0, 1, 3}, {0, 2, 4}, {0, 3, 4}, {1, 2, 5}, {1, 3, 5}, {2, 4, 5}, {3, 4, 5}};

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

  ll n; cin >> n;
  ll c[6];
  for (int i=0;i<6;i++)
    cin >> c[i];

  if (n == 1) {
    cout << reduce(c.begin(), c.end()) - *max_element(c.begin(), c.end());
    return 0;
  }

  ll oneMin = *min_element(c.begin(), c.end());

  ll twoMin = numeric_limits<int>::max();
  for (auto [i, j] : TWO)
    twoMin = min(twoMin, c[i] + c[j]);

  ll threeMin = numeric_limits<int>::max();
  for (auto [i, j, k] : THREE)
    threeMin = min(threeMin, c[i] + c[j] + c[k]);

  ll result = oneMin * ((n - 2) * (n - 2) + (n - 2) * (n - 1) * 4)
              + twoMin * ((n - 2) * 4 + (n - 1) * 4)
              + threeMin * 4;

  cout << result;

  return 0;
}

250222

BOJ 2565 : 전깃줄 (Gold 5)

쌍을 를 기준으로 오름차순 정렬했을 때의 의 LIS를 찾으면 된다.
- 함수 로 봐도 될 듯.

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

typedef pair<int, int> pii;

int n;
int dp[100] = {0, };
pii lines[100];
int dfs(int i) {
  if (i == n-1) return 1;
  if (dp[i] > 0) return dp[i];

  dp[i] = 1;
  for (int j=i+1;j<n;j++)
    if (lines[i].second < lines[j].second)
      dp[i] = max(dp[i], 1+dfs(j));
  return dp[i];
}

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

  cin >> n;
  for (int i=0;i<n;i++) {
    int a, b;
    cin >> a >> b;
    lines[i] = make_pair(b, a);
  }

  sort(lines, lines + n);

  int mm = 0;
  for (int i=0;i<n;i++)
    mm = max(mm, dfs(i));

  cout << (n - mm);

  return 0;
}

SUAPC 2025 Winter

4문제 풀었다. 이거는 따로 후기를 작성했다.

240223

BOJ 2294 : 동전 2 (Gold 5)

쉬운 버전의 냅색 느낌이다.

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

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

  int n, k; cin >> n >> k;
  set<int> s;
  for (int i=0;i<n;i++) {
    int x;
    cin >> x;
    s.insert(x);
  }
  int dp[10001];
  memset(dp, -1, (k+1) * sizeof(int));

  for (auto x : s) {
    if (x > k) continue;
    dp[x] = 1;
    for (int i=1;i<=k;i++) {
      if (i-x>0 && dp[i-x]>0) {
        if (dp[i] == -1) {
          dp[i] = dp[i-x]+1;
        } else {
          dp[i] = min(dp[i], dp[i-x]+1);
        }
      }
    }
  }

  cout << dp[k];

  return 0;
}

그러니까 동일한 단어는 고려하지 않는다는 말이다. ↩
그러지 않으려면 앞선 구현처럼 right-biased median을 사용하면 된다. ↩

2025년 2월 3주차 TIL

TOC