알고리즘/BOJ

백준 2025 서강대학교 K512컵

꾸준함. 2025. 6. 21. 22:33

A. 백준 33990번 3대 512

  • 단순 구현

 

#include <iostream>
using namespace std;
const int TARGET = 512;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
int best = 1e9;
for (int i = 0; i < N; i++)
{
int A, B, C;
cin >> A >> B >> C;
int sum = A + B + C;
if (sum >= TARGET && sum < best)
{
best = sum;
}
}
if (best == 1e9)
{
cout << -1 << "\n";
}
else
{
cout << best << "\n";
}
return 0;
}
view raw .cpp hosted with ❤ by GitHub

 

B. 백준 33991번 전철 통학

  • 민수가 역 i에 걸어가서 도착하는 데 걸리는 시간은 맨해튼 거리 공식에 따라 |X − X_i∣+ |Y −Y_i| 분
  •  i의 전철은 0, Ti, 2Ti, 3Ti,…분에 도착하므로, 민수가 도착 시간 Ai분에 가장 가까우면서도 그 이후 도착하는 전철 시각 K_iT_i / A_i⌉ * T_i
  • 세 개의 역에 대해 각각 이 값을 계산한 뒤 이 가장 빠른 탑승 시간

 

 

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
long long boardingTime(long long d, long long t)
{
if (d % t == 0)
{
return d;
}
return (d / t + 1) * t;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
long long x1, y1, x2, y2, x3, y3;
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
int Q;
cin >> Q;
while (Q--)
{
long long x, y, t1, t2, t3;
cin >> x >> y >> t1 >> t2 >> t3;
long long d1 = llabs(x - x1) + llabs(y - y1);
long long d2 = llabs(x - x2) + llabs(y - y2);
long long d3 = llabs(x - x3) + llabs(y - y3);
long long result = min({ boardingTime(d1, t1), boardingTime(d2, t2), boardingTime(d3, t3) });
cout << result << "\n";
}
return 0;
}
view raw .cpp hosted with ❤ by GitHub

 

C. 백준 33992번 사막 탐험

  • 두 가지 방법 중 소모 체력이 더 작은 쪽이 답
    • 직접 경로: 원과 선분이 교차한다면 “전체 거리 – 원 내부 구간 길이”만큼 소모하고, 교차하지 않으면 전체 거리만큼 소모
    • 오아시스 우회 경로: A에서 원 경계까지, B에서 원 경계까지 각각 최단 거리만큼 걸어서 오아시스 안으로 들어가고, 내부에서는 체력이 전혀 소모되지 않은 뒤 다시 나와 B로 이동하는 방식

 

 

#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
double ax, ay, bx, by, px, py, r;
cin >> ax >> ay >> bx >> by >> px >> py >> r;
auto dist = [&](double x1, double y1, double x2, double y2) {
return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
};
double dAB = dist(ax, ay, bx, by);
double dAP = dist(ax, ay, px, py);
double dBP = dist(bx, by, px, py);
double viaOasis = max(0.0, dAP - r) + max(0.0, dBP - r);
double answer = min(dAB, viaOasis);
cout << fixed << setprecision(10) << answer << "\n";
return 0;
}
view raw .cpp hosted with ❤ by GitHub

 

D. 백준 33993번 지정좌석제

  • 강의실을 R×C 크기의 2차원 그리드로 생각하고, 친구가 이미 앉은 좌표 (x_i, y_i)에는 1을, 그렇지 않은 빈 칸에는 0을 표시한 뒤 2차원 누적합 적용
    • 는 그리드의 (1,1)부터 (i,j)까지 사각형 영역 내에 있는 1의 합

 

  • 를 중심으로 한 W * W 영역은 x1 = max⁡(1, x − k), x2 = min⁡(R, x + k), y1 = max⁡(1, y − k), y2=min⁡(C, y + k)로 경계를 정할 수 있고, 이 영역 안의 친구 수는 S[x2][y2]−S[x1 − 1][y2]−S[x2][y1 − 1]+S[x1 − 1][y1−1]

 

 

#include <iostream>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int N, R, C, W;
cin >> N >> R >> C >> W;
int k = (W - 1) / 2;
vector<vector<char>> grid(R + 1, vector<char>(C + 1, 0));
for (int i = 0; i < N; i++)
{
int x, y;
cin >> x >> y;
grid[x][y] = 1;
}
vector<vector<int>> S(R + 1, vector<int>(C + 1, 0));
for (int i = 1; i <= R; i++)
{
for (int j = 1; j <= C; j++)
{
S[i][j] = grid[i][j] + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];
}
}
int bestCount = -1;
int bestX = 0, bestY = 0;
for (int x = 1; x <= R; x++)
{
for (int y = 1; y <= C; y++)
{
if (grid[x][y] == 0)
{
int x1 = max(1, x - k);
int x2 = min(R, x + k);
int y1 = max(1, y - k);
int y2 = min(C, y + k);
int cnt = S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1];
if (cnt > bestCount
|| (cnt == bestCount
&& (x < bestX || (x == bestX && y < bestY))))
{
bestCount = cnt;
bestX = x;
bestY = y;
}
}
}
}
cout << bestCount << "\n";
cout << bestX << " " << bestY << "\n";
return 0;
}
view raw .cpp hosted with ❤ by GitHub

 

E. 백준 33994번 Magical Trees

  • N이 홀수일 때만 가능하므로, 먼저 홀짝을 판별
  • 홀수인 경우에는 near-perfect matching 3개를 만든 뒤, 이들을 두 개씩 합쳐서 스패닝 트리를 구성하는 기법을 적용
  • 정점 1부터 N까지 있고, 가상의 정점 (N + 1)을 하나 더 추가하여 전체를 짝수 개로 만든 뒤 원형 라운드로빈 방식의 1-factorization 알고리즘으로 3라운드 실행
    • 각 라운드에서 dummy 정점과 매칭된 간선을 제외하면, 남은 (N − 1) / 2개의 간선이 near-perfect matching

 

  • 이렇게 얻은 매칭을 M₀, M₁, M₂라 할 때, T_0 = M_1 ∪ M_2, T_1 = M_0 ∪ M_2, T_2 = M_0 ∪ M_1로 정의하면, 각 T_i는 간선 개수 N − 1개로 스패닝 트리 조건 (연결+무사이클)을 만족하고 동일한 간선은 정확히 두 트리에 속하게 됨

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
if (N % 2 == 0)
{
cout << "No\n";
return 0;
}
cout << "Yes\n";
int Np = N + 1;
int dummy = Np;
vector<int> players(Np);
for (int i = 0; i < Np; i++)
{
players[i] = i + 1;
}
vector<vector<pair<int, int>>> M(3);
for (int r = 0; r < 3; r++)
{
for (int i = 0; i < Np / 2; i++)
{
int u = players[i];
int v = players[Np - 1 - i];
if (u == dummy || v == dummy)
{
continue;
}
if (u > v)
{
swap(u, v);
}
M[r].emplace_back(u, v);
}
int tmp = players[Np - 1];
for (int i = Np - 1; i > 1; i--)
{
players[i] = players[i - 1];
}
players[1] = tmp;
}
vector<vector<pair<int, int>>> T(3);
for (auto e : M[1])
{
T[0].push_back(e);
}
for (auto e : M[2])
{
T[0].push_back(e);
}
for (auto e : M[0])
{
T[1].push_back(e);
}
for (auto e : M[2])
{
T[1].push_back(e);
}
for (auto e : M[0])
{
T[2].push_back(e);
}
for (auto e : M[1])
{
T[2].push_back(e);
}
for (int t = 0; t < 3; t++)
{
for (auto e : T[t])
{
cout << e.first << ' ' << e.second << "\n";
}
}
return 0;
}
view raw .cpp hosted with ❤ by GitHub

 

F. 백준 34000번 취향 변화

  • 주어진 수열에서 각 물건에 대해 좋아하면 +1, 싫어하면 –1의 값을 부여하여 C_1, C_2, …, C_n 이라는 +1, -1 시퀀스를 얻음
  • dong_gas가 왼쪽에서부터 k개를 가져갈 때의 행복도 S(k) = C_1 + ... + C_k
  • shandy5833은 나머지로 전체 - S(k)
  • 두 사람 행복도의 곱 f(k) = S(k) * (전체 −S(k))로 S(k)가 T / 2에 가까울수록 커짐
  • C_i는 1 혹은 -1이고 0에서 출발해 T에 이르는 과정에서 중간의 모든 정수 값을 반드시 한 번 이상 통과한다는 성질에 따라 S(k) = ⌊T / 2⌋ 혹은 ⌈T / 2⌉를 만족하는 k가 항상 존재함을 알 수 있음
  • 따라서 가능한 최대 행복도 곱은 s가 ⌊T / 2⌋, ⌈T / 2⌉일 때 T^2 / 4

 

#include <iostream>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int N, Q;
cin >> N >> Q;
vector<int> a(N + 1);
for (int i = 1; i <= N; i++)
{
cin >> a[i];
}
vector<int> typeSign(N + 1);
for (int t = 1; t <= N; t++)
{
int b;
cin >> b;
typeSign[t] = (b == 1 ? 1 : -1);
}
vector<int> count(N + 1, 0);
for (int i = 1; i <= N; i++)
{
count[a[i]]++;
}
long long totalHappiness = 0;
for (int t = 1; t <= N; t++)
{
totalHappiness += 1LL * count[t] * typeSign[t];
}
while (Q--)
{
int type;
cin >> type;
if (type == 1)
{
int i, j;
cin >> i >> j;
int oldType = a[i];
int newType = j;
if (oldType != newType)
{
int oldSign = typeSign[oldType];
int newSign = typeSign[newType];
totalHappiness += (newSign - oldSign);
count[oldType]--;
count[newType]++;
a[i] = newType;
}
}
else
{
int t;
cin >> t;
int oldSign = typeSign[t];
int cnt = count[t];
totalHappiness -= 2LL * oldSign * cnt;
typeSign[t] = -oldSign;
}
long long T = totalHappiness;
long long answer = (T * T) / 4;
cout << answer << '\n';
}
return 0;
}
view raw .cpp hosted with ❤ by GitHub

 

G. 백준 33995번 LCS Making

  • S에 빠진 글자가 하나라도 있을 경우 빠진 글자를 T의 글자로 마음껏 사용할 수 있음
    • S에 빠진 글자는 LCS에 기여 X
    • 따라서 원하는 K만큼만 S에 실제로 등장하는 어떤 문자로 매칭시키고 나머지 (N – K) 자리를 모두 빠진 문자로 채우면 정확히 LCS 길이 K를 만들 수 있음

 

  • S가 알파벳 26글자를 전부 포함하는 경우에는 빠진 글자가 존재하지 않음
    • 이때는 T에 어느 글자를 넣더라도 S에 해당 글짜가 최소 한 번 이상 나타나므로 LCS는 최소값 f_min 이상이 됨 (여기서 f_min⁡은 S에 등장하는 26개 문자 중 가장 적게 등장한 문자의 빈도)
    • 최소 LCS 길이 = f_min
    • 최대 LCS 길이는 T = S일 때이므로 N

 

  • 최종 판정 조건은 다음과 같음
    • S가 26글자 전부를 포함하지 않는다면, K가 1 이상 N 이하일 때 항상 가능 → 출력 1
    • S가 26글자를 전부 포함한다면, K가 f_min⁡ <= K <= N인 경우에만 가능 → K >= f_min⁡이면 1, 그렇지 않으면 0

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int N, K;
cin >> N >> K;
string s;
cin >> s;
int freq[26] = { 0 };
for (char c : s)
{
freq[c - 'a']++;
}
int uniqueCount = 0;
for (int i = 0; i < 26; i++)
{
if (freq[i] > 0)
{
uniqueCount++;
}
}
if (uniqueCount < 26)
{
cout << 1 << "\n";
}
else
{
int minFreq = freq[0];
for (int i = 1; i < 26; i++)
{
minFreq = min(minFreq, freq[i]);
}
cout << (K >= minFreq ? 1 : 0) << "\n";
}
return 0;
}
view raw .cpp hosted with ❤ by GitHub

 

H. 백준 33996번 점진적인 수열

  • 점진적인 수열이란 길이가 3 이상인 수열 A_1, A_2, …, A_k에 대해 diff_j = A_(j+1) − A_j라 할 때, 모든 j = 1, 2, …, k−2에 대하여 diff_(j+1) ∈ { diff_j − 1,  diff_j,  diff_j + 1}를 만족하는 것
  • 각 위치 j에 대해, 앞선 모든 위치 k < j와의 차이 S_j - S_k를 계산하여 정렬된 리스트 diffList[j]에 저장
    • 해당 리스트를 이용하면 이후 특정 차이값을 이분 탐색으로 찾아낼 수 있음

 

  • “끝나는 위치와 그전 위치 사이의 차이”를 기준으로 같은 종류의 부분 수열을 한데 모아 두고, 그 묶음에 대해 몇 개나 있는지와 그들의 길이를 모두 더한 값을 기록
    • diffList[i]: k < i인 모든 k에 대해 S_i - S_k를 모아 정렬해 둔 목록
    • cntList[i][idx]: 차이 diffList[i][idx]를 가진 부분 수열의 개수
    • lenList[i][idx]: 위 부분 수열들의 길이 합

 

  • 각 쌍 (i, j)에 대하여,
    • (S_j − S_i)에 대해, diffList[i]에서 {S_j − S_i - 1,   S_j − S_i,  S_j − S_i + 1}을 이분 탐색으로 찾아 집계된 (cnt, len)을 꺼내고 newCnt = 1 + ∑cnt, newLen = 2 + ∑(len + cnt)으로 갱신
    • 길이 3 이상이 된 부분 수열에서 늘어난 길이 합 ∑(len + cnt)을 정답에 누적
    • 마지막으로 cntList[j]와 lenList[j]의 (S_j − S_i) 위치를 newCnt, newLen으로 업데이트

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MOD = 1e9 + 7;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
vector<long long> seq(N);
for (int i = 0; i < N; i++)
{
cin >> seq[i];
}
vector<vector<int>> diffList(N);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < i; j++)
{
diffList[i].push_back(int(seq[i] - seq[j]));
}
sort(diffList[i].begin(), diffList[i].end());
}
vector<vector<int>> cntList(N), lenList(N);
for (int i = 0; i < N; i++)
{
int sz = diffList[i].size();
cntList[i].assign(sz, 0);
lenList[i].assign(sz, 0);
}
long long answer = 0;
for (int i = 0; i < N; i++)
{
auto& curDiff = diffList[i];
auto& curCnt = cntList[i];
auto& curLen = lenList[i];
for (int j = i + 1; j < N; j++)
{
int delta = int(seq[j] - seq[i]);
int aggCnt = 0, aggLen = 0;
for (int k = -1; k <= 1; k++)
{
int target = delta + k;
auto it = lower_bound(curDiff.begin(), curDiff.end(), target);
if (it != curDiff.end() && *it == target)
{
int idx = int(it - curDiff.begin());
aggCnt = (aggCnt + curCnt[idx]) % MOD;
aggLen = (aggLen + curLen[idx]) % MOD;
}
}
int newCnt = aggCnt + 1;
if (newCnt >= MOD)
{
newCnt -= MOD;
}
int newLen = (aggLen + aggCnt) % MOD;
newLen = (newLen + 2) % MOD;
int addValue = (aggLen + aggCnt) % MOD;
answer = (answer + addValue) % MOD;
auto& nextDiff = diffList[j];
auto& nextCnt = cntList[j];
auto& nextLen = lenList[j];
int idx2 = int(lower_bound(nextDiff.begin(), nextDiff.end(), delta) - nextDiff.begin());
nextCnt[idx2] = (nextCnt[idx2] + newCnt) % MOD;
nextLen[idx2] = (nextLen[idx2] + newLen) % MOD;
}
}
cout << answer << "\n";
return 0;
}
view raw .cpp hosted with ❤ by GitHub

 

I. 백준 33997번 광부가 될 수 있다면

  • 각 행 간 이동은 “한 칸만 아래로 내려간 후 그 행에서 좌우로 자유롭게 이동”하는 과정
  • 같은 행에서 열 k에서 열 j로 이동하며 얻는 값은 구간 합으로 간단히 표현할 수 있지만, 모든 쌍을 직접 계산하면 O(N^2)이 되어 시간 초과가 발생
  • 구간 합을 최적화하기 위해 “구간 최소값”과 “구간 최대값”을 미리 구해 두고, DP를 활용하면 각 행을 O(N)에 처리 가능

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int N, M;
cin >> N >> M;
vector<long long> dpPrev(M, 0), dpCur(M);
vector<long long> rowValues(M);
vector<long long> prefixSum(M + 1);
vector<long long> leftMin(M), rightMax(M);
vector<long long> prefixMaxU(M), suffixMaxV(M);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> rowValues[j];
}
prefixSum[0] = 0;
for (int j = 0; j < M; j++)
{
prefixSum[j + 1] = prefixSum[j] + rowValues[j];
}
leftMin[0] = prefixSum[0];
for (int j = 1; j < M; j++)
{
leftMin[j] = min(leftMin[j - 1], prefixSum[j]);
}
rightMax[M - 1] = prefixSum[M];
for (int j = M - 2; j >= 0; j--)
{
rightMax[j] = max(rightMax[j + 1], prefixSum[j + 1]);
}
for (int j = 0; j < M; j++)
{
long long uVal = dpPrev[j] - leftMin[j];
if (j == 0)
{
prefixMaxU[j] = uVal;
}
else
{
prefixMaxU[j] = max(prefixMaxU[j - 1], uVal);
}
}
for (int j = M - 1; j >= 0; j--)
{
long long vVal = dpPrev[j] + rightMax[j];
if (j == M - 1)
{
suffixMaxV[j] = vVal;
}
else
{
suffixMaxV[j] = max(suffixMaxV[j + 1], vVal);
}
}
for (int j = 0; j < M; j++)
{
long long candA = prefixMaxU[j] + rightMax[j];
long long candB = suffixMaxV[j] - leftMin[j];
dpCur[j] = max(candA, candB);
}
dpPrev.swap(dpCur);
}
long long answer = *max_element(dpPrev.begin(), dpPrev.end());
cout << answer << "\n";
return 0;
}
view raw .cpp hosted with ❤ by GitHub

 

J. 백준 33998번 거의 같은 문자열

에디토리얼 해설 + gpt 합작품

  • 모든 쿼리를 그 길이에 따라 queriesByLength 맵에 저장
  • 원본 문자열 S에 대해 26글자의 문자별 누적 빈도 prefixCounts[i][c]를 미리 계산
    •  구간일 때, 각 문자 의 개수는prefixCounts[pos + L][c] − prefixCounts[pos][c]

 

  • 각 쿼리 문자열에 대해 26차원 벡터 형태의 서명을 만들고, unordered_map으로 고유 ID를 부여
  • S에서 길이 인 모든 윈도우를 순회하며 앞서 만든 서명과 비교
    • 일치하는 서명이 존재하면 해당 ID의 카운터를 증가

 

  • 각 쿼리에 대응하는 ID의 집계 값을 정답 배열에 채워 출력

 

 

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <array>
using namespace std;
struct signature
{
array<int, 26> a;
bool operator==(signature const& other) const
{
return a == other.a;
}
};
struct signatureHash
{
size_t operator()(signature const& sig) const noexcept
{
size_t h = 0;
for (int c = 0; c < 26; c++)
{
h = h * 1000003 + sig.a[c];
}
return h;
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int N, M;
cin >> N >> M;
string s;
cin >> s;
vector<string> queries(M);
for (int i = 0; i < M; i++)
{
cin >> queries[i];
}
unordered_map<int, vector<int>> queriesByLength;
for (int i = 0; i < M; i++)
{
queriesByLength[queries[i].size()].push_back(i);
}
vector<array<int, 26>> prefixCounts(N + 1);
for (int c = 0; c < 26; c++)
{
prefixCounts[0][c] = 0;
}
for (int i = 0; i < N; i++)
{
prefixCounts[i + 1] = prefixCounts[i];
prefixCounts[i + 1][s[i] - 'a']++;
}
vector<long long> answer(M, 0);
for (auto& entry : queriesByLength)
{
int len = entry.first;
auto& indices = entry.second;
if (len > N)
{
continue;
}
unordered_map<signature, int, signatureHash> signatureToId;
signatureToId.reserve(indices.size() * 2);
vector<int> signatureIdForQuery(indices.size());
int idCount = 0;
for (int j = 0; j < (int)indices.size(); j++)
{
signature querySignature;
querySignature.a.fill(0);
for (char ch : queries[indices[j]])
{
querySignature.a[ch - 'a']++;
}
auto it = signatureToId.find(querySignature);
if (it == signatureToId.end())
{
signatureToId[querySignature] = idCount;
signatureIdForQuery[j] = idCount;
++idCount;
}
else
{
signatureIdForQuery[j] = it->second;
}
}
vector<long long> countForSignature(idCount, 0);
signature windowSignature;
for (int pos = 0; pos + len <= N; pos++)
{
for (int c = 0; c < 26; c++)
{
windowSignature.a[c] = prefixCounts[pos + len][c] - prefixCounts[pos][c];
}
auto it = signatureToId.find(windowSignature);
if (it != signatureToId.end())
{
++countForSignature[it->second];
}
}
for (int j = 0; j < (int)indices.size(); j++)
{
answer[indices[j]] = countForSignature[signatureIdForQuery[j]];
}
}
for (auto val : answer)
{
cout << val << '\n';
}
return 0;
}
view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2022

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

반응형

'알고리즘 > BOJ' 카테고리의 다른 글

백준 Hello, AlKon! 2025  (0) 2025.05.17
백준 2025 중앙대학교 프로그래밍 경진대회  (1) 2025.04.13
백준 월간 향유회 2025. 01.  (0) 2025.02.02
백준 7469번 K번째 수  (1) 2025.01.18
백준 1017번 소수 쌍  (0) 2024.10.30