프로그래밍

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

[난이도] Gold5
[유형] 스택

[풀이]
stack을 이용해 모든 괄호쌍의 위치를 저장한 뒤,
괄호쌍을 고르는 모든 경우의 수를 브루트포스를 이용해 구해준 뒤,
선택된 괄호쌍의 괄호들을 제거한 string을 set에 저장한 뒤 순회하며 출력해주면 됩니다.
괄호쌍의 최대 개수가 10개로 제한되어 있으므로 브루트포스를 이용할 수 있습니다.

#include <iostream>
#include <string>
#include <stack>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
string s;
vector<pair<int,int>> v;
int main(){
    cin >> s;
    stack<int> st;
    for(int i=0;i<s.size();i++){
        char c = s[i];
        if(c=='(') st.push(i);
        else if(c==')'){
            v.push_back({st.top(),i});
            st.pop();
        }
    }
    set<string> ans;
    int n = v.size();
    for(int i=1;i<(1<<n);i++){
        vector<bool> erased(s.size());
        for(int j=0;j<n;j++){
            if(((1<<j)&i)>0) erased[v[j].first]=erased[v[j].second]=1;
        }
        string tmp;
        for(int j=0;j<s.size();j++){
            if(!erased[j]) tmp+=s[j];
        }
        ans.insert(tmp);
    }
    for(auto a : ans) cout << a << '\n';
}

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

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

[난이도] Gold5
[유형] BFS

[풀이]
2인 점부터 시작해 갈수 있는 1인 점들을 순차적으로 방문하는 BFS를 이용하면 답을 구할 수 있습니다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int N,M,board[1001][1001],sy,sx;
int dy[4]={-1,1,0,0};
int dx[4]={0,0,1,-1};
int visit[1001][1001];
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) {
            scanf("%d",&board[i][j]);
            if(board[i][j]==2) sy=i,sx=j;
        }
    queue<pair<int,int>> q;
    q.push({sy,sx});

    int dist=1;
    while(!q.empty()){
        int sz=q.size();
        while(sz--){
            auto [y,x] = q.front(); q.pop();
            for(int i=0;i<4;i++){
                int ny=y+dy[i];
                int nx=x+dx[i];
                if(ny<0||nx<0||ny>=N||nx>=M||board[ny][nx]!=1||visit[ny][nx]) continue;
                q.push({ny,nx});
                visit[ny][nx]=dist;
            }
        }
        dist++;
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(visit[i][j]==0 && board[i][j]==1) printf("-1 ");
            else printf("%d ",visit[i][j]);
        }
        puts("");
    }
}

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

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

[난이도] Gold5
[유형] 수학

[풀이]
1~1000000의 수에 대해 각각의 모든 약수를 구해서 미리 저장해놔야 하는데
일반적으로 루트N에 모든 약수를 구하는 방법으로
각각의 수에 대해 구할 경우 O(루트(1000000))의 복잡도가 필요합니다.
위 방법을 사용할 경우 O(1000000*1000) 의 시간이 걸리므로 시간내에 해결이 불가능합니다.
에라토스테네스의 체를 이용해 소수를 구할때와 비슷한 방식으로
f[1000001] 배열을 미리 선언해놓고 1~1000000까지를 순회하면서
i에 대해 f[i*1],f[i*2],f[i*3].. (i*k <=1000000) 에 i를 더해주면 f 배열을 채울 수 있습니다.
이를 이용해 부분합 배열 s를 만들어 채워주면 쿼리에 대한 답을 O(1)에 구할 수 있습니다.

#include <cstdio>
using ll = long long;
int T,f[1000001];
ll s[1000001];
int main(){
    scanf("%d",&T);
    for(int i=1;i<=1e6;i++)
        for(int j=i;j<=1e6;j+=i) f[j]+=i;
    for(int i=1;i<=1e6;i++) s[i]=f[i]+s[i-1]; 
    while(T--){
        int v;
        scanf("%d",&v);
        printf("%lld\n",s[v]);
    }
}

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

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

[난이도] Gold5
[유형] DP

[풀이]
전형적인 배낭 문제입니다.
물건을 여러개를 선택할 수 있기 때문에
두번째 for문에서 for(int j=m;j>=0;j--) 이 아닌 for(int j=0;j<=m;j++) 를 사용하여
물건이 여러개 중복될 수 있도록 해야합니다.

또한 float을 100을 곱해 정수로 변환시 부동소수점 문제로 정확하지 않은 값으로 변환 될 수 있으므로
0.5를 더해주어야 합니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,dp[10001],cal[5000],price[5000];
int main(){
    while(1){
        float f;
        scanf("%d%f",&n,&f);
        if(n==0) break;
        m=f*100+0.5;
        for(int i=0;i<n;i++) {
            scanf("%d%f",&cal[i],&f);
            price[i]=100*f;
        }
        memset(dp,0,sizeof(dp));
        int ans=0;

        for(int i=0;i<n;i++){
            for(int j=1;j<=m;j++){
                if(j-price[i]>=0) {
                    dp[j] = max(dp[j],dp[j-price[i]]+cal[i]);
                    ans=max(ans,dp[j]);
                }
            }
        }
        printf("%d\n",ans);
    }
}

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

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

[난이도] Gold5
[유형] 브루트포스

[풀이]
직사각형 3개로 나눌 수 있는 모양은 총 6가지가 나옵니다.
수평, 혹은 수직으로 3개로 나누는 2개 이외에,
ㅏ ㅓ ㅜ ㅗ 모양의 4가지 모양이 더 있을 수 있다는 것을 주의해야 합니다.
N,M 제한이 50밖에 되지 않으므로,
2중, 3중 for문을 적절히 활용해서 구간을 나누어 브루트포스로 구해주면 됩니다.

#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;
int N,M;
ll a[50][50];
ll sol(int sy,int sx,int ey,int ex){
    ll sum=0;
    for(int i=sx;i<=ex;i++)
        for(int j=sy;j<=ey;j++)
            sum+=a[j][i];
    return sum;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) scanf("%1lld",&a[i][j]);

    ll ans=0;
    for(int i=0;i<N-2;i++)
        for(int j=i+1;j<N-1;j++)
            ans=max(ans,sol(0,0,i,M-1)*sol(i+1,0,j,M-1)*sol(j+1,0,N-1,M-1));

    for(int i=0;i<M-2;i++)
        for(int j=i+1;j<M-1;j++)
            ans=max(ans,sol(0,0,N-1,i)*sol(0,i+1,N-1,j)*sol(0,j+1,N-1,M-1));

    for(int i=0;i<N-1;i++){
        for(int j=0;j<M-1;j++) ans=max(ans,sol(0,0,i,M-1)*sol(i+1,0,N-1,j)*sol(i+1,j+1,N-1,M-1));
        for(int j=0;j<M-1;j++) ans=max(ans,sol(i+1,0,N-1,M-1)*sol(0,0,i,j)*sol(0,j+1,i,M-1));
    }
    for(int i=0;i<M-1;i++){
        for(int j=0;j<N-1;j++) ans=max(ans,sol(0,0,N-1,i)*sol(0,i+1,j,M-1)*sol(j+1,i+1,N-1,M-1));
        for(int j=0;j<N-1;j++) ans=max(ans,sol(0,i+1,N-1,M-1)*sol(0,0,j,i)*sol(j+1,0,N-1,i));
    }
    printf("%lld",ans);
}

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

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

[난이도] Gold5
[유형] 위상정렬

[풀이]
위상정렬

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int N,M,ans[1001],inDegree[1001];
vector<int> adj[1001];
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        inDegree[v]++;
    }
    queue<int> q;
    for(int i=1;i<=N;i++) {
        if(!inDegree[i]) {
            q.push(i);
            ans[i]=1;
        }
    }
    int cur=2;
    while(!q.empty()){
        int sz=q.size();
        while(sz--){
            int qf = q.front();
            q.pop();
            for(auto nxt : adj[qf]){
                if(--inDegree[nxt]==0){
                    q.push(nxt);
                    ans[nxt]=cur;
                }
            }
        }
        cur++;
    }
    for(int i=1;i<=N;i++) printf("%d ",ans[i]);
}

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

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

[난이도] Gold5
[유형] Greedy

[풀이]
K개의 조로 나눈다는 것을 결국 K-1개의 경계를 골라야 한다는 의미입니다.
키가 작은 순서로 0번부터 N-1번 원생이 서있다면,
경계를 나누지 않을 경우의 비용은 a[N-1]-a[0] 입니다. (a[i] : i번 원생의 키)
만약 i와 i-1 사이에 경계를 추가한다면 a[i]-a[i-1] 만큼은 비용에서 제외됩니다.
결국 K개의 조로 나눴을 때 가장 비용을 적게 하려면
K-1의 경계 중 가장 비용이 큰 경계를 고르면 됩니다.
a[i]-a[i-1] (i:1~N-1) 의 값을 배열에 저장한 뒤, 정렬하여 K-1개의 큰 비용을 구해서
전체 비용에서 빼주면 쉽게 구할 수 있습니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,K,a[300000],ans;
int main(){
    scanf("%d%d",&N,&K);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    sort(a,a+N);
    ans = a[N-1]-a[0];
    for(int i=N-1;i>=1;i--) a[i]=a[i]-a[i-1];
    a[0]=0;
    sort(a,a+N);
    for(int i=N-1;K>1;K--,i--) ans-=a[i];
    printf("%d",ans);
}

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

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

[난이도] Gold5
[유형] DFS

[풀이]
두 로봇 중 한 로봇의 시작점에서 DFS를 시작하여 다른 로봇에 도착할 때까지
지나는 엣지들의 합 total과 엣지중의 최댓값 val을 갱신해줍니다.
다른 로봇에 도착했을 때까지 갱신된 total-val이 정답입니다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,s,e,ans;
vector<pair<int,int>> adj[100001];
void sol(int n,int prev,int val,int total){
    if(n==e){
        ans=total-val;
        return;
    }
    for(auto [nxt,d] : adj[n]){
        if(nxt!=prev) {
            sol(nxt,n,max(val,d),total+d);
        }
    }
}
int main(){
    scanf("%d%d%d",&N,&s,&e);
    for(int i=0;i<N-1;i++){
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        adj[u].push_back({v,d});
        adj[v].push_back({u,d});
    }
    sol(s,0,0,0);
    printf("%d",ans);
}

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