프로그래밍

www.acmicpc.net/problem/2473

[난이도] Gold4

[유형] 이분탐색

[풀이]

a+b+C의 절댓값이 0에 가장 가까운 a,b,c를 찾는 문제
N이 5000이므로 N^3으로 풀수가 없다. => 이분탐색 이용
a,b를 결정하고 (N^2) 그 a,b일 때 가장 최적의 c를 이분탐색으로
찾는다(lgN).
s=a+b 일때 0~N-1중 -s의 lower_bound를 찾는다. lower_bound의 위치가
idx이고 a[idx] != -s인 경우에는 idx-1이 최적일수도 있다.
또한 a[idx] == s이어도 idx가 a또는 b인 경우에는 최적이 될 수 없다.
그러므로 넉넉하게 idx-5 ~ idx+5까지 체크하면서 a,b가 아니면서 절댓값이
최소가 되는 c를 찾아야 한다.

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
using ll = long long;
int N,a[5000],r[3];
ll mxN = 9e10;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    sort(a,a+N);

    for(int i=0;i<N-1;i++){
        for(int j=i+1;j<N;j++){
            ll s = a[i]+a[j];
            int idx = lower_bound(a,a+N,-s)-a;
            for(int k=idx-5;k<idx+5;k++){
                if(k<0||k>=N||k==i||k==j) continue;
                ll ss = abs(s+a[k]);
                if(ss < mxN){
                    mxN = ss;
                    r[0]=i,r[1]=j,r[2]=k;
                }
            }
        }
    }
    sort(r,r+3);
    for(int i=0;i<3;i++) printf("%d ",a[r[i]]);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2473.cpp

www.acmicpc.net/problem/2458

[난이도] Gold4

[유형] DFS

[풀이]

in,out 배열을 만들고 각 점에서 DFS를 해서 방문할 수 있는 점의 개수를
out에, DFS중 어떤 점을 방문할때 그 점의 in값을 1씩 증가 시킨다.
in[i]+out[i]==N인 점이 정답인 점들이다.

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int N,M,in[501],out[501],ans;
vector<int> adj[501];
bool visit[501];
int dfs(int n){
    visit[n] = 1;
    int ret = 1;
    for(int nxt : adj[n]){
        if(!visit[nxt]){
            in[nxt]++;
            ret+=dfs(nxt);
        }
    }
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<M;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        adj[a].push_back(b);
    }

    for(int i=1;i<=N;i++){
        memset(visit,0,sizeof(visit));
        out[i] = dfs(i);
    }
    for(int i=1;i<=N;i++) if(in[i]+out[i]==N) ans++;
    printf("%d",ans);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2458.cpp

www.acmicpc.net/problem/2239

[난이도] Gold4

[유형] 백트래킹

[풀이]

81개중 빈칸에 대해 1~9의 숫자를 넣어보면서 조건에 맞는지 체크해간다.

#include <cstdio>
using namespace std;
int map[9][9],ok;
bool check(int y,int x,int k){
    for(int i=0;i<9;i++) {
        if(map[y][i]==k || map[i][x]==k) return 0;
    }
    int yy = (y/3)*3, xx=(x/3)*3;
    for(int i=yy;i<yy+3;i++)
        for(int j=xx;j<xx+3;j++) if(map[i][j]==k) return 0;
    
    return 1;
}
void sol(int y,int x){
    if(ok) return;
    if(y==9) {
        for(int i=0;i<9;i++) {
            for(int j=0;j<9;j++) printf("%d",map[i][j]);
            puts("");
        }
        ok = 1;
        return;
    }
    if(map[y][x]){
        if(x==8) sol(y+1,0);
        else sol(y,x+1);
    }else{
        for(int i=1;i<10;i++){
            if(check(y,x,i)){
                map[y][x] = i;
                if(x==8) sol(y+1,0);
                else sol(y,x+1);
                map[y][x] = 0;
            }
        }
    }
}
int main(){
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++) scanf("%1d",&map[i][j]);
    sol(0,0);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2239.cpp

www.acmicpc.net/problem/2234

[난이도] Gold4

[유형] DFS

[풀이]

1. DFS를 돌면서 각 방이 어떤 그룹에 속하는지 나누면서 각 그룹에 몇개의
   방이 있는지를 체크한다.
2. 모든 방을 순회하면서 동,서,남,북 방향을 체크해 다른 그룹이 있으면
   현재 방의 개수 + 현재 체크중인 인접한 방의 개수를 더해 답을
   갱신해준다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,map[50][50],g,grp[2501],mxR,mxS;
int visit[50][50];
int dy[4] = {0,-1,0,1};
int dx[4] = {-1,0,1,0};
int dfs(int y,int x){
    visit[y][x] = g;
    int ret = 1;
    for(int i=0;i<4;i++){
        if((map[y][x] & (1<<i))==0){
            int ny = y+dy[i], nx = x+dx[i];
            if(ny < 0 || nx < 0 || ny >= n || nx >= m || visit[ny][nx]) continue;
            ret+=dfs(ny,nx);
        }
    }
    return ret;
}
int main(){
    scanf("%d%d",&m,&n);
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&map[i][j]);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!visit[i][j]){
                g++;
                grp[g] = dfs(i,j);
                mxR = max(mxR,grp[g]);
            }
        }
    }
    for(int y=0;y<n;y++){
        for(int x=0;x<m;x++){
            for(int i=0;i<4;i++){
                if((map[y][x] & (1<<i))>0){
                    int ny = y+dy[i], nx = x+dx[i];
                    if(ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
                    if(visit[ny][nx] != visit[y][x]) mxS = max(mxS,grp[visit[ny][nx]]+grp[visit[y][x]]);
                }
            }
        }
    }
    printf("%d\n%d\n%d",g,mxR,mxS);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2234.cpp

www.acmicpc.net/problem/2075

[난이도] Gold4

[유형] 우선순위큐

[풀이]

메모리 제한이 12MB으로 적으므로 우선순위 큐를 이용해서 푼다.
큐의 크기가 N 이하이면 무조건 push,
아닌 경우 top보다 작은 것들은 무시, top보다 크면 pop하고 push한다
모든 수를 다 봤을 때 top이 정답이다.

#include <cstdio>
#include <queue>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
int N;
int main(){
    priority_queue<int,vector<int>,greater<int>> a;
    scanf("%d",&N);
    for(int i=0;i<N*N;i++) {
        int v;
        scanf("%d",&v);
        if(a.size()<N) a.push(v);
        else if(a.top() < v) {
            a.pop();
            a.push(v);
        }
    }
    printf("%d",a.top());
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2075.cpp

www.acmicpc.net/problem/2056

[난이도] Gold4

[유형] 위상정렬

[풀이]

위상정렬로 각 작업을 방문하면서 total 배열에 그 작업에 도착하기 까지의 시간을 기록하면 된다.

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int N,work[10001],total[10001],in[10001],ret;
vector<int> adj[10001];
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        int ac,pre;
        scanf("%d%d",&work[i],&ac);
        in[i] = ac;
        for(int j=0;j<ac;j++){
            scanf("%d",&pre);
            adj[pre].push_back(i);
        }
    }
    queue<int> q;
    for(int i=1;i<=N;i++) if(!in[i]) q.push(i);
    while(!q.empty()){
        int qf = q.front(); q.pop();
        ret = max(ret,total[qf]+work[qf]);
        for(auto nxt : adj[qf]){
            total[nxt] = max(total[nxt],total[qf]+work[qf]);
            if(--in[nxt]==0) q.push(nxt);
        }

    }   
    printf("%d",ret);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2056.cpp

www.acmicpc.net/problem/1976

[난이도] Gold4

[유형] DFS

[풀이]

여행해야하는 임의의 한 점에서 DFS를 돌았을 때 여행 경로에 있는 모든 점을 Visit한 경우에만 YES이다.

#include <cstdio>
using namespace std;
int N,M,d[1001];
bool adj[201][201],visit[201];
void dfs(int n){
    visit[n] = 1;
    for(int i=1;i<=N;i++)
        if(adj[n][i] && !visit[i]) dfs(i);
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) scanf("%d",&adj[i][j]);
    for(int i=0;i<M;i++) scanf("%d",&d[i]);
    dfs(d[0]);
    for(int i=0;i<M;i++) {
        if(!visit[d[i]]) {
            puts("NO");
            return 0;
        }
    }
    puts("YES");
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1976.cpp

www.acmicpc.net/problem/1967

[난이도] Gold4

[유형] 트리의 지름(DFS)

[풀이] 

트리의 지름 : 트리에서 거리가 가장 먼 두 점 사이의 거리. 구

하는 방법 : 임의의 점에서 DFS로 가장 먼 점을 찾은 뒤에 그 점에서 DFS를 이용해서 가장 먼 점을 찾으면 그 거리가 트리의 지름이 된다.

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int N,ans,mxN,mxV;
bool visit[10001];
vector<pair<int,int>> adj[10001];
void dfs(int n,int c){
    visit[n] = 1;
    if(c>mxV){
        mxV=c;
        mxN=n;
    }
    for(auto nxt : adj[n]){
        if(!visit[nxt.first]) dfs(nxt.first,c+nxt.second);
    }
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N-1;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    dfs(1,0);
    memset(visit,0,sizeof(visit));
    mxV=0;
    dfs(mxN,0);
    printf("%d",mxV);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1967.cpp