devbelly

문제 https://www.acmicpc.net/problem/5859 알고리즘 Union Find 풀이 쿼리를 순서대로 반영했을 때, 모순이 일어나지 않는 최대 갯수를 구하는 문제입니다. 유니온 파인드에서 종종 보이는 유형입니다. 하나의 사람을 두 가지 타입으로 나눕니다. $u$에 대해 참말을 하는 T(u)와 거짓말을 하는 F(u)로 나눕니다. 이에 따라 가능한 경우의 수를 묶고 모순이 발생하는지 확인하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i > u >> v >> x; if (x == 'T') { uni(T(u), T(v)); u..

문제 https://www.acmicpc.net/problem/8895 알고리즘 DP 풀이 서로 다른 $N$개의 막대를 좌우로 쌓을 때, 옆에서 보이는 l, r의 경우의 수를 구하는 문제입니다. $cache[n][l][r]$을 선언하여 풀되, 다음 상태(n+1)를 갱신할 때는 기존 막대의 크기를 1씩 키우고 가장 작은 막대(높이 1)를 추가하는 것으로 생각하여 풀면 쉽게 풀 수 있습니다. 막대를 가장 왼쪽, 오른쪽에 배치하는 것은 직관적이나 막대를 막대들 사이에 넣을 때 가장 작은 막대를 추가한다면 기존 상태 $cache[n][l][r]$에서 $cache[n+1][l][r]$ 만 갱신하기 때문에 신경쓸 것이 적어집니다. 코드 #include #define rep(i, n) for (int i = 0; i..

문제 https://www.acmicpc.net/problem/1856 알고리즘 DP 풀이 주어진 문자열을 단어 리스트를 조합하여 만들기 위한 최소 제거 횟수를 묻는 문제입니다. 2차원 배열의 구간DP를 선언하여 $i~j$까지 만들기 위한 최소 제거 횟수를 구하여 풀었지만 2차원 배열 대신 1차원 배열로도 풀 수 있습니다. 주어진 단어 w를 사용할 때, 중간에 끊는 것 없이 한번 사용하면 무조건 끝까지 매칭하여야 하기 때문입니다. cache[i] = 문자열 S의 $i$번째까지 만들기 위한 최소 제거 횟수 주어진 단어 w를 전부 매칭했다면 (idx값이 -1) 제거한 문자 수를 계산하여 cache값을 업데이트하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i ..

문제 https://www.acmicpc.net/problem/20366 알고리즘 정렬 풀이 서로 다른 네 수를 뽑아 두 개씩 짝지었을 때, 차이를 최소화 하는 문제입니다. NC2를 통해 가능한 조합을 뽑고 나서 인덱스들이 가리키는 수들의 합을 기준으로 정렬한 후 풀면 됩니다. 정렬된 배열(벡터)에서 각 수의 조합이 서로 다른 인덱스로 이루어졌는지 확인하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i N; rep(i, N) { int x; cin >> x; vt.emplace_back(x); } for (int i = 0; i < vt.size() - 1; ++i) { ..

문제 https://www.acmicpc.net/problem/1398 알고리즘 DP, Greedy 풀이 최소 동전의 수를 묻는 문제입니다. 주어진 동전들이 Canonical 하다면 그리디하게 풀 수 있습니다. 이 문제에서는 그렇지 않으므로 DP를 이용해서 풀어야합니다. 일반적으로 주어진 금액의 크기만큼 배열크기를 선언하지만 이 문제에서는 금액의 크기가 $10^{15}$이므로 배열선언도 어렵습니다. 1, 10, 25, 100, 1000, 2500, 10000, 100000, ... 하지만 동전들을 3개씩 나누어 본다면 배수관계를 만족함을 알 수 있습니다. (1 10 25), (100 1000 2500), (10000 100000 ...) 즉 DP를 100씩 끊어서 사용하면 됩니다. 코드 #include ..

문제 https://www.acmicpc.net/problem/5900 알고리즘 DP 풀이 1비트를 k개 사용했을 때, n번째 비트를 구하는 문제입니다. 일단 n번째 비트의 자릿수 먼저 구해야 합니다. 만약 자릿수가 5이고 사용한 k가 3일 때 5자리로 나타낼 수 있는 가짓수는 4C2입니다. 왜냐하면 맨 처음 1은 무조건 나와야 하기 때문입니다. 그렇다면 자릿수를 구하기 위해서는 2C2 + 3C2 + 4C2.. 와같이 세 자리에서 k 3개일 때 경우의 수 + 네 자리에서 k 3개 일 때 경우의 수 + 다섯 자리에서 k 3개일 때의 경우의 수처럼 앞에서부터의 누적합을 구해야 nth가 몇 번째 자릿수인지 구할 수 있습니다. 하지만 굳이 누적합을 구하지 않더라도 이미 누적합이 구해져 있습니다. 5C3은 2C2..

문제 https://www.acmicpc.net/problem/5854 알고리즘 Sorting 풀이 $K$번 겹치는 선분의 길이를 구하는 문제입니다. 세그먼트트리 문제에서 직사각형 관련 문제를 풀 때 비슷하게 풀어본 적이 있는 것 같습니다. 주어진 선분을 모두 구한 후 각 선분마다 선분의 왼쪽 점과 오른쪽 점을 구분합니다. 벡터에 넣어 정렬한 후, 만일 현재점이 선분의 왼쪽을 구성하는 점이라면 $psum$값을 1증가시키고 선분의 오른쪽을 구성하는 점이라면 $psum$값을 1감소시킵니다. $psum$은 현재 겹쳐진 횟수를 의미하며 해당 값이 $K$이상일때만 $ans$에 기록하여 문제를 풀었습니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #de..

문제 https://www.acmicpc.net/problem/5849 알고리즘 stack 풀이 inversion을 만들지 않는 소의 개수를 구하는 문제입니다. $a_i$를 u, $b_i$를 v라고 하겠습니다. inversion을 만들지 않기 위해서는 u를 기준으로 정렬했을 때, v가 오름차순의 형태를 가져야만합니다. 오름차순을 유지하기 위해 스택을 사용해서 문제를 풀면 됩니다. 스택의 top이 현재 보고 있는 소의 v보다 크다면 이는 inversion을 만들기 때문에 계속 pop을 해주고, 지금까지 확인한 v값들보다 현재 v값이 작다면 현재 v는 inversion을 만들지 않으므로 스택에 push 해주면 됩니다. 아래 코드는 이 해설과는 다른 코드입니다. 풀이만 참고하세요. 코드 #include #de..