BOJ 2342 : Dance Dance Revolution (Gold 3)

• DP 문제인데 애먹어서 못 풀다가 이제 풀었다.

• 을 번째 위치를 밟을 때, 그리고 마지막 두 발의 위치가 일 때의 최소의 총 힘이라고 정의하자. 그러면 다음과 같은 transition rule을 생각할 수 있다.

  • 여기서 는 허용 상태 집합이며 다음과 같이 정의된다.

• 각 상태는 직전 에만 영향을 받으므로 모두 저장할 필요 없다.

from math import inf

l = [int(x) for x in input().split()][:-1]
dp = [[inf] * 5 for i in range(5)]
dp[0][0] = 0

def cost(x, y):
  if x == 0:
    return 2
  if x == y:
    return 1
  return 3 + ((x-y)%2 == 0)

for x in l:
  tmp = [[inf] * 5 for i in range(5)]
  for j in range(5):
    for k in range(5):
      if j == k and j != 0:
        continue
      tmp[x][j] = min(tmp[x][j], dp[k][j] + cost(k, x))
      tmp[j][x] = min(tmp[j][x], dp[j][k] + cost(k, x))
  dp=tmp

print(min([min(x) for x in dp]))

BOJ 2170 : 선 긋기 (Gold 5)

• 스위핑 기초다. 이벤트 리스트가 포인트이다.

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

  vector<pi> events;
  int n; cin >> n;

  for (int i=0;i<n;i++) {
    int l, r; cin >> l >> r;
    events.emplace_back(l, 1);
    events.emplace_back(r, -1);
  }

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

  int cur = 0, start = 0, res = 0;
  for (auto [p, e] : events) {
    if (e == 1 && cur == 0) start = p;
    cur += e;
    if (e == -1 && cur == 0) res += p - start;
  }
  cout << res;

  return 0;
}

BOJ 20412 : 추첨상 사수 대작전! (Hard) (Gold 2)

이 두 식을 빼면,

1. 일때,

   이므로, 해 는 무수히 많다. 으로 잡을 수 있다.

2. 일때,

   페르마의 소정리에 의해,

   는 첫 식에 대입해서 구하면 된다.

m, s, x1, x2 = map(int, input().split())
if s==x1:
  print(1, 0)
else:
  a = (x1-x2)*pow((s-x1)%m,-1,m)%m
  c = (x1-a*s)%m
  print(a,c)

BOJ 13975 : 파일 합치기 3 (Gold 4)

• 허프만 코딩 문제다.

• 허프만 코딩 증명은 다음과 같이 하면 된다. 이거 하면서 교환 논법 감 잡은듯.

  • 다음을 증명한다.

    주어진 가중치 , , 에 대해 항상 가장 작은 두 개를 합쳐 가중치 인 새 노드를 만들고, 이걸 반복해서 만든 이진트리가 전체 가중 경로 길이 를 최소로 한다.

  • 이를 위해 다음 두 Lemma를 증명한다.

    1. 가장 작은 두 가중치는 최적 트리에서 형제(같은 부모)로 둘 수 있다.
       • 얘는 교환 논법으로 증명할 수 있는데, 최적 트리의 가장 깊은 리프가 가중치가 가장 작지 않을 경우, 그렇게 바꾼 뒤 비용 변화가 얼마가 될지 구하면 된다.
    2. 두 최소 가중치를 하나로 합치면 부분문제도 최적이다.
       • 이 부분은 직관적으로 알 수 있다.

  • Lemma를 모두 증명한 뒤엔 수학적 귀납법으로 마무리하면 된다.

from heapq import heapify, heappop, heappush

t=int(input())
for _ in range(t):
  n=int(input())
  q=[int(x) for x in input().split()]
  heapify(q)
  res=0
  while len(q)>1:
    a,b=heappop(q),heappop(q)
    heappush(q, a+b)
    res+=a+b
  print(res)

BOJ 11401 : 이항 계수 3 (Gold 1)

• 단계별로 풀어보기에서 힌트를 줘서 풀었다.

• 이항계수를 구하면 다음과 같다. 역원은 페르마의 소정리로 구하면 된다.

n,k=map(int,input().split())
res=1
p=int(1e9)+7
for i in range(n-k+1,n+1):
  res=(res*i)%p
k_fac=1
for i in range(1,k+1):
  k_fac=(k_fac*i)%p
res=(res*pow(k_fac,p-2,p))%p
print(res)

BOJ 1069 : 집으로 (Gold 3)

• Exhaustive하게 케이스 분류를 하자면, ()일 때, 일 때를 나누고, 그 안에서 0번 점프, 1번 점프, ...를 나누어서 최소 시간 케이스를 고르면 된다.
• 일 때에는 0번 점프, 1번 점프, 2번 점프 중 하나가 최적이고, 그 이상 점프하면 2번 점프보다 항상 비효율적이다.
• 일 때에는 0번 점프, 번 점프, 점프 중 하나가 최적이다. ()

x,y,d,t=map(int,input().split())
l=(x*x+y*y)**.5
if d>l:
  print(min(t+d-l,l,2*t))
else:
  n=int(l/d)
  print(min(n*t+l-n*d,(n+1)*t,l))

BOJ 1562 : 계단 수 (Gold 3)

• 을 마지막(번째) 자리수, 를 0-9 중 등장한 수의 집합(비트셋)이라고 할 때, 를 해당 조건을 만족하는 계단 수의 개수라고 정의하자.

• 그러면 다음과 같은 transition rule이 생각난다.

  • 이때 이고, 범위에 벗어나는 경우 0으로 가정하면 된다.

• 연산자 우선순위 때문에 한참 애먹었다. 까불지 말고 괄호 많이 치자.

#include <bits/stdc++.h>

using namespace std;

// dp[last digit][bitset of 0-9]
int dp[10][1024] = {0, };
int cur[10][1024] = {0, };

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

  int n; cin >> n;

  for (int l=1;l<10;l++)
    dp[l][1<<l] = 1;

  for (int i=1;i<n;i++) {
    memset(cur, 0, sizeof(cur));
    for (int l=0;l<10;l++) {
      for (int b=0;b<1<<10;b++) {
        if ((b&(1<<l)) == 0) continue;
        if (l>0) {
          cur[l][b] = (cur[l][b] + dp[l-1][b]) % 1000000000;
          cur[l][b] = (cur[l][b] + dp[l-1][b&~(1 << l)]) % 1000000000;
        }
        if (l<9) {
          cur[l][b] = (cur[l][b] + dp[l+1][b]) % 1000000000;
          cur[l][b] = (cur[l][b] + dp[l+1][b&~(1 << l)]) % 1000000000;
        }
      }
    }
    memcpy(dp, cur, sizeof(cur));
  }

  int res = 0;
  for (int i=0;i<10;i++) {
    res = (res + dp[i][1023]) % 1000000000;
  }

  cout << res;

  return 0;
}

BOJ 2162 : 선분 그룹 (Platinum 5)

• 선분 교차 + DSU 하면 된다.
• 선분 교차 알고리즘에 실수가 많아서 많이 틀렸다. 사고과정(아니면 알고리즘 자체)를 익숙하게 만들어야 한다.

#include <bits/stdc++.h>

using namespace std;

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

struct DisjointSet {
  vi parent, rank;

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

  int merge(int u, int v) {
    u=find(u), v=find(v);
    if (u == v) return rank[u];
    if (rank[u]>rank[v]) swap(u,v);
    parent[u] = v;
    rank[v] += rank[u];
    return rank[v];
  }
};

int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
  int res = (x2-x1)*(y3-y1) - (x3-x1)*(y2-y1);
  if (res > 0) return 1;
  if (res < 0) return -1;
  return 0;
}

bool intersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
  int ccw1 = ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4);
  int ccw2 = ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2);
  if (ccw1 == 0 && ccw2 == 0) {
    pi p1 = {x1, y1};
    pi p2 = {x2, y2};
    pi p3 = {x3, y3};
    pi p4 = {x4, y4};

    if (p1 > p2) swap(p1, p2);
    if (p3 > p4) swap(p3, p4);
    return !(p2 < p3 || p4 < p1);
  }
  return ccw1 <= 0 && ccw2 <= 0;
}

int coord[3000][4];

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

  int n; cin >> n;
  for (int i=0;i<n;i++)
    for (int j=0;j<4;j++)
      cin >> coord[i][j];
  
  DisjointSet ds(n);
  int m = 1;
  for (int i=0;i<n;i++)
    for (int j=i+1;j<n;j++)
      if (intersect(coord[i][0], coord[i][1], coord[i][2], coord[i][3], coord[j][0], coord[j][1], coord[j][2], coord[j][3]))
        m = max(m, ds.merge(i, j));

  set<int> si;
  for (int i=0;i<n;i++)
    si.insert(ds.find(i));

  cout << si.size() << '\n' << m;

  return 0;
}

BOJ 4195 : 친구 네트워크 (Gold 2)

• Map + DSU로 풀면 된다.

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

struct DisjointSet {
  vi parent, rank;

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

  int merge(int u, int v) {
    u=find(u), v=find(v);
    if (u == v) return rank[u];
    if (rank[u]>rank[v]) swap(u,v);
    parent[u] = v;
    rank[v] += rank[u];
    return rank[v];
  }
};

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

  int T; cin >> T;
  while (T--) {
    DisjointSet ds(200000);
    map<string,int> ms;
    int f; cin >> f;
    for (int i=0;i<f;i++) {
      string a, b;
      cin >> a >> b;
      if (!ms.count(a)) ms[a] = ms.size();
      if (!ms.count(b)) ms[b] = ms.size();
      ds.merge(ms[a], ms[b]);
      cout << ds.rank[ds.find(ms[a])] << '\n';
    }
  }

  return 0;
}

BOJ 14890 : 경사로 (Gold 3)

• 구현만 열심히 해주면 된다.

#include <bits/stdc++.h>

using namespace std;

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

int mat[100][100];

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

  int n, l; cin >> n >> l;
  for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
      cin >> mat[i][j];
  
  int ans = 0;
  for (int i=0;i<n;i++) {
    int prev = mat[i][0];
    bool okay = true;
    bool ramp[100] = {false, };
    for (int j=1;j<n;j++) {
      if (mat[i][j] > prev) {
        if (mat[i][j] > prev + 1) {
          okay = false; break;
        }
        for (int k=1;k<=l;k++) {
          if (j-k<0 || ramp[j-k] || mat[i][j-k] != prev) {
            okay = false; break;
          }
          ramp[j-k] = true;
        }
        if (!okay) break;
      } else if (mat[i][j] < prev) {
        if (mat[i][j] < prev - 1) {
          okay = false; break;
        }
        for (int k=0;k<l;k++) {
          if (j+k>n-1 || ramp[j+k] || mat[i][j+k] != prev-1) {
            okay = false; break;
          }
          ramp[j+k] = true;
        }
        if (!okay) break;
      }
      prev = mat[i][j];
    }
    if (okay) ans++;
  }

  for (int i=0;i<n;i++) {
    int prev = mat[0][i];
    bool okay = true;
    bool ramp[100] = {false, };
    for (int j=1;j<n;j++) {
      if (mat[j][i] > prev) {
        if (mat[j][i] > prev + 1) {
          okay = false; break;
        }
        for (int k=1;k<=l;k++) {
          if (j-k<0 || ramp[j-k] || mat[j-k][i] != prev) {
            okay = false; break;
          }
          ramp[j-k] = true;
        }
        if (!okay) break;
      } else if (mat[j][i] < prev) {
        if (mat[j][i] < prev - 1) {
          okay = false; break;
        }
        for (int k=0;k<l;k++) {
          if (j+k>n-1 || ramp[j+k] || mat[j+k][i] != prev-1) {
            okay = false; break;
          }
          ramp[j+k] = true;
        }
        if (!okay) break;
      }
      prev = mat[j][i];
    }
    if (okay) ans++;
  }

  cout << ans;

  return 0;
}

BOJ 13977 : 이항 계수와 쿼리 (Platinum 5)

• 위의 ‘이항 계수 3’ 문제와 거의 동일하지만 팩토리얼만 전처리 해주면 된다.
• 채점하는 데에 10분 넘게 걸린듯...

MOD = 1_000_000_007
fac = [0]*4_000_001
fac[0] = 1
for i in range(1, 4_000_001):
  fac[i] = fac[i-1] * i % MOD

for _ in range(int(input())):
  n, k = map(int, input().split())
  print(fac[n]*pow(fac[k] * fac[n-k],MOD-2,MOD)%MOD)

• 이 문제로 인해 플래티넘 4를 달성하게 되었다. 한 달에 티어 하나씩 오르게 하고 싶다.