고등부 5번 청개구리를 제외한 문제들의 풀이이다.
2309 - 일곱 난쟁이 (초1, Bronze I)
문제
- 9명 중 7명의 키를 합했을 때 100이고 유일하다. 이때 7개의 수를 오름차순으로 출력하시오.
풀이
더보기
9명 중 7명을 고르는 것과 9명 중 2명을 제외하는 것은 같으므로 2명을 제외하는 모든 경우를 고려한다. 시간복잡도는 O(9^2)이다.
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x << ": " << x << "\n"
typedef long long ll;
typedef pair<ll,ll> P;
ll n;
int main(){
fast;
n=9;
vector<ll> v(n);
for(auto &i : v)cin>>i;
sort(all(v));
ll s = accumulate(all(v),0LL);
for(int i = 0 ; i < n ; i++){
for(int j = i+1 ; j < n ; j++){
if(s-v[i]-v[j] == 100){
for(int k = 0 ; k < n ; k++)if(k!=i and k!=j)cout<<v[k]<<"\n";
return 0;
}
}
}
}
2605 - 줄 세우기 (초2, Bronze II)
문제
- N(<=100)명이 있다. 1번부터 번호를 뽑아 맨 뒤에서 뽑은 번호만큼 앞에 있는 자리에 설 때, 최종 순서를 출력하라.
풀이
더보기
뒤집어서 앞에서부터 뽑은 번호만큼 뒤에 있는 자리로 간다고 생각하고 거꾸로 출력하자. 이는 vector.insert 함수를 이용하면 쉽게 구현할 수 있다. 시간복잡도는 O(N^2)이다.
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x << ": " << x << "\n"
typedef long long ll;
typedef pair<ll,ll> P;
ll n;
int main(){
fast;
cin>>n;
vector<ll> v;
for(int i = 1 ; i <= n ; i++){
ll a; cin>>a; v.insert(v.begin()+a, i);
}
for(int i = n-1 ; i >= 0 ; i--)cout<<v[i]<<" ";
}
2606 - 바이러스 (초3, Silver III)
문제
- 그래프가 주어질 때, 1번이 포함된 (컴포넌트의 크기-1)을 출력하시오.
풀이
더보기
그래프 탐색 기초 문제이다. dfs를 하면서 탐색한 정점 개수를 리턴해주면 된다. 시간복잡도는 O(N+M)이다.
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x << ": " << x << "\n"
typedef long long ll;
typedef pair<ll,ll> P;
ll n, m;
vector<ll> adj[101];
bool visited[101];
ll dfs(ll x){
visited[x]=1;
ll ret=1;
for(auto next : adj[x])if(!visited[next])ret += dfs(next);
return ret;
}
int main(){
fast;
cin>>n>>m;
for(int i = 0 ; i < m ; i++){
ll a,b; cin>>a>>b; adj[a].push_back(b); adj[b].push_back(a);
}
cout<<dfs(1)-1;
}
2607 - 비슷한 단어 (초4/중2, Silver II)
문제
- 두 단어가 문자 종류가 같고 같은 문자가 같은 개수만큼 있으면 같은 구성이라고 한다. 두 단어 중 하나에 최대 한 개의 문자를 추가/삭제/변경하여 같은 구성이 되면 비슷한 단어라고 한다. 단어가 N개 주어질 때 1번 단어와 비슷한 단어의 개수를 구하시오.
풀이
더보기
조금 귀찮다. 일단 순서가 중요한 건 아니므로 알파벳 개수를 비교하자. 알파벳 개수의 차가 2 미만이면 비슷한 단어이다. 차가 2 초과이면 비슷한 단어가 아니다.
차가 2일 때가 중요한데, 먼저 aaa와 a처럼 한 알파벳이 2 이상 차이가 나는 경우는 비슷한 단어가 아니다. 그게 아니라면 차가 1인 두 알파벳이 있을 텐데, 이 때는 한 알파벳을 다른 알파벳으로 바꿨을 때 같은 구성이 되는지를 보면 된다. (아래 코드의 26번 줄) 시간복잡도는 O(N|S|)이다.
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x << ": " << x << "\n"
typedef long long ll;
typedef pair<ll,ll> P;
ll n;
ll cnt[27];
vector<string> v;
ll f(ll x){
ll cnt2[27]={};
for(auto i : v[x])cnt2[i-'A']++;
ll d = 0;
vector<ll> v;
for(int i = 0 ; i < 26 ; i++){
if(abs(cnt[i]-cnt2[i])>=2)return 0;
d += abs(cnt[i]-cnt2[i]);
if(cnt[i]^cnt2[i])v.push_back(i);
}
if(d==2 and cnt[v[0]]+cnt[v[1]] != cnt2[v[0]]+cnt2[v[1]])return 0;
return d<=2;
}
int main(){
fast;
cin>>n;
v.resize(n);
for(auto &i : v)cin>>i;
ll ans=0;
for(auto i : v[0])cnt[i-'A']++;
for(int i = 1 ; i < n ; i++)ans += f(i);
cout<<ans;
}
2608 - 로마 숫자 (초5/고2, Gold V)
문제
- 로마 숫자 2개가 주어지면, 그 합을 아라비아 숫자와 로마 숫자로 출력하시오.
풀이
더보기
이 문제는 다시 풀고 싶지 않아서 뉴비 때 작성한 아래 코드로 대체한다. 이 코드보다 10배는 쉽게 짤 수 있으니 아래 코드는 구경만 하자. 시간복잡도는 O(|A|+|B|)이다.
#include <bits/stdc++.h>
using namespace std;
int c, d, e, chk;
string a, b;
int main(){
cin>>a>>b;
for(int i = 0 ; i < a.size() ; i++){
if(a[i] == 'I' and a[i+1] == 'V')c += 4, i++;
else if(a[i] == 'I' and a[i+1] == 'X')c += 9, i++;
else if(a[i] == 'X' and a[i+1] == 'L')c += 40, i++;
else if(a[i] == 'X' and a[i+1] == 'C')c += 90, i++;
else if(a[i] == 'C' and a[i+1] == 'D')c += 400, i++;
else if(a[i] == 'C' and a[i+1] == 'M')c += 900, i++;
else if(a[i] == 'I')c += 1;
else if(a[i] == 'V')c += 5;
else if(a[i] == 'X')c += 10;
else if(a[i] == 'L')c += 50;
else if(a[i] == 'C')c += 100;
else if(a[i] == 'D')c += 500;
else if(a[i] == 'M')c += 1000;
}
for(int i = 0 ; i < b.size() ; i++){
if(b[i] == 'I' and b[i+1] == 'V')d += 4, i++;
else if(b[i] == 'I' and b[i+1] == 'X')d += 9, i++;
else if(b[i] == 'X' and b[i+1] == 'L')d += 40, i++;
else if(b[i] == 'X' and b[i+1] == 'C')d += 90, i++;
else if(b[i] == 'C' and b[i+1] == 'D')d += 400, i++;
else if(b[i] == 'C' and b[i+1] == 'M')d += 900, i++;
else if(b[i] == 'I')d += 1;
else if(b[i] == 'V')d += 5;
else if(b[i] == 'X')d += 10;
else if(b[i] == 'L')d += 50;
else if(b[i] == 'C')d += 100;
else if(b[i] == 'D')d += 500;
else if(b[i] == 'M')d += 1000;
}
e = c + d;
cout<<e<<endl;
if(e >= 1000){
if(e >= 1000)cout<<'M', e -= 1000;
if(e >= 1000)cout<<"M", e -= 1000;
if(e >= 1000)cout<<"M", e -= 1000;
}
if(e >= 100){
if(e < 200)cout<<"C", chk = 1;
else if(e < 300)cout<<"CC", chk = 2;
else if(e < 400)cout<<"CCC", chk = 3;
else if(e < 500)cout<<"CD", chk = 4;
else if(e < 600)cout<<"D", chk = 5;
else if(e < 700)cout<<"DC", chk = 6;
else if(e < 800)cout<<"DCC", chk = 7;
else if(e < 900)cout<<"DCCC", chk = 8;
else if(e < 1000)cout<<"CM", chk = 9;
}
e -= chk*100;
chk = 0;
if(e >= 10){
if(e < 20)cout<<"X", chk = 1;
else if(e < 30)cout<<"XX", chk = 2;
else if(e < 40)cout<<"XXX", chk = 3;
else if(e < 50)cout<<"XL", chk = 4;
else if(e < 60)cout<<"L", chk = 5;
else if(e < 70)cout<<"LX", chk = 6;
else if(e < 80)cout<<"LXX", chk = 7;
else if(e < 90)cout<<"LXXX", chk = 8;
else if(e < 100)cout<<"XC", chk = 9;
}
e -= chk*10;
if(e >= 1){
if(e < 2)cout<<"I";
else if(e < 3)cout<<"II";
else if(e < 4)cout<<"III";
else if(e < 5)cout<<"IV";
else if(e < 6)cout<<"V";
else if(e < 7)cout<<"VI";
else if(e < 8)cout<<"VII";
else if(e < 9)cout<<"VIII";
else if(e < 10)cout<<"IX";
}
}
2609 - 최대공약수와 최소공배수 (중1/고1, Bronze I)
문제
- 두 수의 최대공약수와 최소공배수를 출력한다.
풀이
더보기
std::gcd, std::lcm이라는 좋은 함수가 있다. __gcd도 있다.
제한이 10000 정도로 작아서 직접 나눠보는 방법도 가능하긴 하다. 시간복잡도는 O(log max(A,B))이다.
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
#define debug(x) cout << #x << ": " << x << "\n"
typedef long long ll;
typedef pair<ll,ll> P;
ll a,b;
int main(){
fast;
cin>>a>>b;
cout<<gcd(a,b)<<endl<<lcm(a,b);
}
2610 - 회의준비 (중3/고3, Gold II)
문제
- 정점이 N(<=100)개인 그래프가 주어진다. 각 컴포넌트에서, 다른 정점으로 가는 거리의 최대가 최소인 정점을 구하시오.
풀이
더보기
N 제한이 작으므로, 모든 정점을 고려해볼 수 있다. 플로이드나 bfs로 각 정점쌍의 거리를 구해두고 최댓값을 구한 후 그 중 최소인 정점을 고르면 된다. 시간복잡도는 O(N^3)이다.
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
#define debug(x) cout << #x << ": " << x << "\n"
typedef long long ll;
typedef pair<ll,ll> P;
ll n,m;
ll dist[101][101];
int main(){
fast;
cin>>n>>m;
fill(&dist[0][0], &dist[100][101],1e18);
for(int i = 0 ; i < m ; i++){
ll a,b; cin>>a>>b;
dist[a][b] = dist[b][a] = 1;
}
for(int i = 1 ; i <= n ; i++)dist[i][i] = 0;
for(int k = 1 ; k <= n ; k++){
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++)dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
}
}
vector<bool> visited(n+1,0);
vector<ll> ans;
for(int i = 1 ; i <= n ; i++){
if(visited[i])continue;
vector<ll> v;
for(int j = 1 ; j <= n ; j++)if(dist[i][j] != 1e18)v.push_back(j),visited[j]=1;
ll res = 1e18, idx=0;
for(auto i : v){
ll s=0;
for(auto j : v){
s = max(s,dist[i][j]);
}
if(s<res)res=s,idx=i;
}
ans.push_back(idx);
}
cout<<ans.size()<<endl;
sort(all(ans));
for(auto i : ans)cout<<i<<"\n";
}
2611 - 자동차경주 (중4, Gold II)
문제
- 1번 정점에서 출발하여 어떤 정점을 지나 다시 1번으로 돌아올 수 있는 그래프가 주어진다. 1번 정점에서 시작하고 끝나는 최장 경로의 거리를 출력하고 그 경로에 포함된 정점을 출력하시오.
풀이
더보기
1번 정점으로 들어오는 간선을 N+1번 정점으로 따로 분리하면 이 그래프는 DAG(방향 비순환 그래프)가 된다. 따라서 위상정렬을 하면서 dp를 해줄 수 있고, 역추적을 해주면 된다. 시간복잡도는 O(N+M)이다.
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
#define debug(x) cout << #x << ": " << x << "\n"
typedef long long ll;
typedef pair<ll,ll> P;
ll n, m;
ll dp[1010];
ll prv[1010];
vector<pair<ll,ll>> adj[1010];
ll ind[1010];
int main(){
fast;
cin>>n>>m;
for(int i = 0 ; i < m ; i++){
ll a,b,c; cin>>a>>b>>c;
if(b==1)b=n+1;
adj[a].push_back({b,c}); ind[b]++;
}
memset(dp,-1,sizeof(dp));
dp[1]=0;
queue<ll> q;
q.push(1);
for(int i = 1 ; i <= n+1 ; i++){
auto cur = q.front(); q.pop();
for(auto [next, w] : adj[cur]){
if(dp[next] < dp[cur]+w)dp[next] = dp[cur]+w, prv[next] = cur;
if(--ind[next]==0)q.push(next);
}
}
cout<<dp[n+1]<<"\n";
vector<ll> v;
for(ll i = n+1 ; i != 1 ; i = prv[i])v.push_back(i);
v.push_back(1);
for(int i = v.size()-1 ; i >= 0 ; i--){
if(v[i]>n)v[i] -= n;
cout<<v[i]<<" ";
}
}
2612 - DNA 유사도 (중5, Platinum IV)
문제
- A,C,G,T 4개의 문자로 이루어진 문자열이 2개 주어진다. 각각의 문자열에서 임의의 연속된 부분문자열을 골라서 공백을 잘 넣어 길이가 같게 만든 후 대응시켰을 때, 각 문자가 공백 제외 같으면 +3점, 아니면 -2점으로 정의하여 점수를 계산한다. 최대 점수를 출력하고, 최대 점수가 되는 부분문자열을 출력하시오.
풀이
더보기
이 문제는 Smith-Waterman Algorithm이라고 이름도 있다고 한다. 그건 잘 모르겠고 dp이다.
각 문자열을 S,T라고 하면 dp[i][j] := S[i]로 끝나고 T[j]로 끝나는 부분문자열의 최대 유사도로 정의할 수 있다.
LCS의 아류작 느낌이 나므로 (i-1,j-1), (i-1,j), (i,j-1)을 보면서 직접 테이블을 채우다 보면 다음과 같은 식을 얻을 수 있다.
dp[i][j] = dp[i-1][j-1] + 3(S[i]==T[j])
dp[i][j] = max(0, max(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])-2) (else)
역추적도 해주면 답을 얻을 수 있다. 이때 dp값이 0이 될경우 그 위치에서 다시 시작한다고 생각해야 한다. 시간복잡도는 O(NM)이다.
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
#define debug(x) cout << #x << ": " << x << "\n"
typedef int ll;
typedef pair<ll,ll> P;
ll n, m;
ll dp[1010][1010];
string s,t;
P prv[1010][1010];
int main(){
fast;
cin>>n>>s>>m>>t; s = '#'+s, t = '$'+t;
ll ans = 0, ansi=0,ansj=0;
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= m ; j++){
if(s[i]==t[j]){
ll M = dp[i-1][j-1];
if(M>0)prv[i][j] = {i-1,j-1}, dp[i][j]=M+3;
else dp[i][j]=3;
}
else{
ll M=0, pi = 0, pj=0;
if(M<dp[i-1][j-1])M = dp[i-1][j-1], pi=i-1,pj=j-1;
if(M<dp[i-1][j])M = dp[i-1][j], pi=i-1,pj=j;
if(M<dp[i][j-1])M = dp[i][j-1], pi=i,pj=j-1;
if(M>2)dp[i][j] = M-2, prv[i][j] = {pi,pj};
else dp[i][j]=0;
}
if(ans<dp[i][j])ansi=i,ansj=j,ans=dp[i][j];
}
}
cout<<ans<<"\n";
string rs, rt; rs += s[ansi], rt += t[ansj];
for(ll i = ansi, j = ansj ; prv[i][j] != P{0,0} ;){
auto [ni,nj] = prv[i][j];
if(i!=ni and ni>0)rs += s[ni];
if(j!=nj and nj>0)rt += t[nj];
i=ni,j=nj;
}
reverse(all(rs)); reverse(all(rt));
cout<<rs<<"\n"<<rt;
}
2613 - 숫자구슬 (고4, Gold II)
문제
- 길이 N인 수열이 주어진다. 이 수열을 연속한 M개의 그룹으로 나눌 때, 각 그룹의 합 중 최댓값이 최소가 되도록 할 때 그 값과 각 그룹의 크기를 출력하시오.
풀이
'대회 > KOI' 카테고리의 다른 글
| 와 이걸 왜 대회 때 못풀었지 (0) | 2024.07.06 |
|---|---|
| KOI 2024 일기 (1) | 2024.05.12 |
| KOI 지역본선 2005 (0) | 2023.10.09 |
| KOI 2023 2차 대회 중등부 후기 (2) | 2023.07.17 |
