프로그래밍

https://www.acmicpc.net/problem/12764

[난이도] Gold3
[유형] 시뮬레이션

[풀이]
set 2개를 이용해 현재 빈자리와 현재 사용중인 자리를 저장해주면서
시뮬레이션을 해주었습니다. 삽입/삭제를 O(logN)에 할 수 있도록 set을 이용하였습니다.
우선순위 큐를 이용하여도 됩니다.

#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int N,pos[100001],cnt[100001];
vector<pair<int,int>> v;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        int s,e;
        scanf("%d%d",&s,&e);
        v.push_back({s,i});
        v.push_back({e,i});
    }
    set<int> empty,use;
    sort(v.begin(),v.end());
    for(auto [t,i] : v){
        if(pos[i]){
            use.erase(pos[i]);
            empty.insert(pos[i]);
        }else{
            if(empty.size()>0){
                pos[i]=*empty.begin();
                empty.erase(pos[i]);
            }else if(use.size()>0){
                pos[i]=*(--use.end())+1;
            }else{
                pos[i]=1;
            }
            use.insert(pos[i]);
            cnt[pos[i]]++;
        }
    }
    vector<int> ans;
    for(int i=1;;i++){
        if(!cnt[i]) break;
        ans.push_back(cnt[i]);
    }
    printf("%d\n",ans.size());
    for(auto a : ans) printf("%d ",a

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/12764.cpp

https://www.acmicpc.net/problem/12784

[난이도] Gold3
[유형] DP

[풀이]
dp[i] : i번 노드에서 leaf 노드까지 연결된 간선만 끊을 수 있을 때, 필요한 최소 cost

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int T,N,M,D,dp[1001];
vector<pair<int,int>> adj[1001];
int sol(int n,int p){
    int& ret = dp[n];
    if(ret!=-1) return ret;
    ret=0;
    if(p!=0&&adj[n].size()==1) ret=1e8;
    else{
        for(auto [nxt,d] : adj[n]){
            if(nxt!=p) ret+=min(d,sol(nxt,n));
        }
    }
    return ret;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&N,&M);
        for(int i=1;i<=N;i++) adj[i].clear();
        while(M--){
            int u,v,d;
            scanf("%d%d%d",&u,&v,&d);
            adj[u].push_back({v,d});
            adj[v].push_back({u,d});
        }
        memset(dp,-1,sizeof(dp));
        printf("%d\n",sol(1,0));
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/12784.cpp

https://www.acmicpc.net/problem/2026

[난이도] Gold3
[유형] 백트래킹

[풀이]
인접행렬에 친구관계를 저장 해준 뒤, 재귀를 이용한 백트래킹을 해주면 됩니다.
현재까지 확정된 친구를 frd vector에 저장해준 뒤, 현재 친구가 될 수 있는지 확인중인 친구가
이 frd vector의 친구와 모두 친구인지 확인해서, 모두 친구이면 다음 함수를 호출해줍니다.
frd vector의 크기가 K(<=62)가 되면 조건을 만족하는 친구집합을 구한 것이므로 출력하고 종료해줍니다.
frd vector의 크기가 최대 62를 넘어갈 수 없으므로 시간내에 해결이 가능합니다.

#include <cstdio>
#include <vector>
using namespace std;
int K,N,F,adj[901][901];
vector<int> frd;
bool sol(int cur){
    if(frd.size()==K) return 1;
    for(int i=cur+1;i<=N;i++){
        bool ok=1;
        for(auto a : frd){
            if(!adj[i][a]){
                ok=0;
                break;
            }
        }
        if(ok) {
            frd.push_back(i);
            if(sol(i)) return 1;
            frd.pop_back();
        }
    }
    return 0;
}
int main(){
    scanf("%d%d%d",&K,&N,&F);
    while(F--){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u][v]=adj[v][u]=1;
    }
    for(int i=1;i<=N;i++){
        frd.push_back(i);
        if(sol(i)){
            for(auto f : frd) printf("%d\n",f);
            return 0;
        }
        frd.clear();
    }
    puts("-1");
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/2026.cpp

https://www.acmicpc.net/problem/20057

[난이도] Gold3
[유형] 시뮬레이션

[풀이]
우선 토네이도의 규칙성을 파악해야 합니다.
<-,ㅜ,->,ㅗ 방향을 각각 0,1,2,3 이라고 정하고
격자의 크기가 N일 때, (N/2+1,N/2+1) 에서부터
0->1->2->3->0 순서로 방향을 바꾸며 진행됩니다.
각 방향으로 진행하는 횟수는 1,1,2,2,3,3,4,4....N-1,N-1,N-1 로
방향이 2회 바뀔때마다 횟수가 1번씩 늘어나며 마지막 N-1번 진 행할때는 3번 방향이 바뀝니다.

위를 이용해 시뮬레이션을 해주면 되는데

map<int,vector<pair<int,int>>> table =
{
    {1,{{1,1},{-1,1}}},
    {2,{{2,0},{-2,0}}},
    {7,{{1,0},{-1,0}}},
    {10,{{1,-1},{-1,-1}}},
    {5,{{0,-2}}}
};

위와 같이 현재 방향이 0일때의 {퍼센트,{토네이도로부터의 상대좌표}} 들을 map을 이용해 저장해 놓고
시계방향으로 90도 회전할때마다 (y,x) -> (-x,y)로 좌표들을 변경해서 이용해주면 됩니다.
즉, 방향이 0일때는 0번, 1일때는 1번, 2일때는 2번, 3일때는 3번 회전시켜주면 되므로
위의 1개의 테이블만 정의해주면 됩니다.

#include <map>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
int N,board[501][501],ans;
int dy[4] = {0,1,0,-1};
int dx[4] = {-1,0,1,0};
map<int,vector<pair<int,int>>> table = 
{
    {1,{{1,1},{-1,1}}},
    {2,{{2,0},{-2,0}}},
    {7,{{1,0},{-1,0}}},
    {10,{{1,-1},{-1,-1}}},
    {5,{{0,-2}}}
};
pair<int,int> cvt(int dir,int y,int x){
    for(int i=0;i<dir;i++) {
        int ny=-x,nx=y;
        y=ny,x=nx;
    }
    return {y,x};
}
void update(int dir,int fy,int fx){
    int total=board[fy][fx];
    int erased=0;
    for(auto [k,v] : table){
        for(auto p : v){
            auto c = cvt(dir,p.first,p.second);
            int ny=fy+c.first, nx=fx+c.second;
            int r = total*(k/100.0);
            erased+=r;
            if(ny>=1&&nx>=1&&ny<=N&&nx<=N) board[ny][nx]+=r;
            else ans+=r;
        }
    }
    board[fy][fx]=0;
    int ty=fy+dy[dir],tx=fx+dx[dir];
    if(ty>=1&&tx>=1&&ty<=N&&tx<=N) board[ty][tx]+=total-erased;
    else ans+=total-erased;
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) scanf("%d",&board[i][j]);
    int cy=N/2+1,cx=N/2+1,dir=0;
    for(int i=1;i<N;i++){
        int cnt=2;
        if(i==N-1) cnt=3;
        for(int j=0;j<cnt;j++){
            for(int k=0;k<i;k++){
                cy+=dy[dir];
                cx+=dx[dir];
                update(dir,cy,cx);
            }
            dir=(dir+1)%4;
        }
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/20057.cpp

https://www.acmicpc.net/problem/1325

[난이도] Silver1
[유형] DFS

[풀이]
dfs를 이용해 각 노드부터 시작해서 방문할 수 있는 총 노드의 개수를 구할 수 있습니다.
이 노드의 개수가 해킹할 수 있는 노드의 개수입니다.

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
using namespace std;
int N,M,visit[10001];
vector<int> adj[10001];
map<int,vector<int>> mp;
int dfs(int n){
    visit[n]=1;
    int ret=1;
    for(auto nxt : adj[n]){
        if(!visit[nxt]){
            ret+=dfs(nxt);
        }
    }
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int u,v;scanf("%d%d",&u,&v);adj[v].push_back(u);
    }
    for(int i=1;i<=N;i++){
        memset(visit,0,sizeof(visit));
        mp[dfs(i)].push_back(i);
    }
    auto [k,res] = *mp.rbegin();
    sort(res.begin(),res.end());
    for(auto a : res) printf("%d ",a);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/1325.cpp

https://www.acmicpc.net/problem/2947

[난이도] Silver5
[유형] 구현

[풀이]
문제의 조건대로 구현해주면 됩니다.

#include <cstdio>
int a[5];
void prt(){
    for(int i=0;i<5;i++) printf("%d ",a[i]);
    puts("");
}
bool cmp(int i,int j){
    if(a[i]>a[j]){
        int tmp=a[i];
        a[i]=a[j];
        a[j]=tmp;
        return true;
    }
    return false;
}
int main(){
    for(int i=0;i<5;i++) scanf("%d",&a[i]);
    while(1){
        bool ok=0;
        for(int i=0;i<4;i++){
            if(cmp(i,i+1)) {
                ok=1;
                prt();
            }
        }
        if(!ok) break;
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver5/2947.cpp

https://www.acmicpc.net/problem/15922

[난이도] Gold5
[유형] 스위핑

[풀이]
pair 배열에 (시작점,끝점)을 넣어둔 뒤, 시작점을 기준으로 오름차순을 해줍니다.
그 뒤에 스위핑을 이용하여 겹치는 부분을 처리해서 하나의 선분으로 묶어주면
전체 길이를 쉽게 구할 수 있습니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N;
pair<int,int> v[100000];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d%d",&v[i].first,&v[i].second);
    sort(v,v+N);
    int ans=0,s=v[0].first,e=v[0].second;
    for(int i=0;i<N;i++){
        if(v[i].first <= e) {
            if(v[i].second > e) e=v[i].second;
        }else{
            ans+=e-s;
            s=v[i].first;
            e=v[i].second;
        }
    }
    printf("%d",ans+e-s);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/15922.cpp

https://www.acmicpc.net/problem/17069

[난이도] Gold5
[유형] DP

[풀이]
DP[r][c][k] : 파이프의 끝이 r,c에 있고 모양이 k일때 (N,N)에 도착할 수 있는 경우의 수, (0:가로,1:세로,2:대각선)
현재 모양 k에 따라 dp 점화식을 세워주면 됩니다.

#include <cstdio>
#include <cstring>
using namespace std;
using ll = long long;
int N,board[35][35];
ll dp[35][35][3];
ll sol(int r,int c,int k){
    if(r==N&&c==N) return 1;
    ll& ret = dp[r][c][k];
    if(ret!=-1) return ret;
    ret=0;
    if(k==0){
        if(!board[r][c+1]) {
            ret+=sol(r,c+1,0);
            if(!board[r+1][c+1] && !board[r+1][c]) ret+=sol(r+1,c+1,2);
        }
    }
    if(k==1){
        if(!board[r+1][c]) {
            ret+=sol(r+1,c,1);
            if(!board[r+1][c+1] && !board[r][c+1]) ret+=sol(r+1,c+1,2);
        }
    }
    if(k==2){
        if(!board[r][c+1]) ret+=sol(r,c+1,0);
        if(!board[r+1][c]) ret+=sol(r+1,c,1);
        if(!board[r+1][c+1] && !board[r+1][c] && !board[r][c+1]) ret+=sol(r+1,c+1,2);        
    }
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) 
            scanf("%d",&board[i][j]);
    for(int i=1;i<=N+1;i++) board[N+1][i]=board[i][N+1]=1;
    memset(dp,-1,sizeof(dp));
    printf("%lld",sol(1,2,0));
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/17069.cpp