프로그래밍

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

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

[풀이]
DFS 재귀함수를 이용해서 가능한 모든 경우를 구해준다. 일반 DFS와 다르게 함수 return시 visit[i]=0으로 다시 설정해주어야 한다. 왜냐하면 새로운 경우의 경로에서는 이전에 방문했던 곳도 다시 방문할 수 있기 때문이다.
소숫점 9자리까지 출력해야 하는것에 주의해야한다.

  
    #include <cstdio>

    int N,dy[4]={0,0,1,-1};
    int dx[4]={1,-1,0,0},visit[40][40];
    int p[4],cnt;
    double ans;
    void sol(int y,int x,int k,double pr){
        visit[y][x]=1;
        if(k==N){
            visit[y][x]=0;
            cnt++;
            ans+=pr;
            return;
        }
        
        for(int i=0;i<4;i++){
            int ny=y+dy[i], nx=x+dx[i];
            if(!visit[ny][nx]){
                sol(ny,nx,k+1,pr*(p[i]/(double)100));
            }
        }
        visit[y][x]=0;
    }
    int main(){
        scanf("%d",&N);
        for(int i=0;i<4;i++) scanf("%d",&p[i]);
        sol(17,17,0,1);
        printf("%.11f",ans);
    }

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

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

[난이도] Gold4
[유형] 분할정복

[풀이]
preorder 배열에서는 맨 앞의 원소가 root이다.
inorder 배열에서 root값을 찾으면 그 root값을 기준으로 좌측이 left child, 우측이 right child이다.
이 성질을 이용하여, 재귀함수로 left child, right child의 preoder,inorder 각각의 배열에서의 범위를 전달하는 방식으로 답을 구한다.

#include <cstdio>
int tc,N,pre[1001],in[1001];
void post(int lp,int rp,int li,int ri){
    if(lp>rp) return;
    if(lp==rp) {
        printf("%d ",pre[lp]);
        return;
    }

    int root = pre[lp];
    int idx=li;

    for(int i=li;i<=ri;i++){
        if(root==in[i]){
            idx=i;
            break;
        }
    }
    int lcnt = idx-li;

    post(lp+1,lp+lcnt,li,idx-1);
    post(lp+lcnt+1,rp,idx+1,ri);
    printf("%d ",pre[lp]);
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);
        for(int i=0;i<N;i++) scanf("%d",&pre[i]);
        for(int i=0;i<N;i++) scanf("%d",&in[i]);
        post(0,N-1,0,N-1);
        puts("");
    }
}

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

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

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

[풀이]
N자리수 수를 모두 검사하면 시간초과가 나므로
필요없는 것을 걸러주면서 모든 가능한 케이스를 찾아야 한다.
1. prev,cur vector를 선언, prev에는 (i-1) 자리수의 소수를 저장하고,
cur에는 prev에 1자리수를 추가해서 새롭게 확인된 i자리수의 소수를 저장한다.

2. prev,cur 초기화는 {2,3,5,7}로 하고, 뒤에 수를 새롭게 더할 때는 홀수만을 더한다. (짝수가 1의 자리에 오면 소수가 될 수 없다.)

3. prev의 수들에 홀수들 더한 수가 소수인지를 체크할때는 sqrt를 이용해서 연산 시간을 줄인다.

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
int N;
bool prime(int n){
    for(int i=2;i<=sqrt(n);i++)
        if(n%i==0) return 0;
    return 1;
}
int main(){
    scanf("%d",&N);
    vector<int> prev,cur;
    prev = {2,3,5,7};
    cur=prev;
    for(int i=1;i<N;i++){   
        cur.clear();
        for(int v : prev) {
            for(int j=1;j<10;j+=2){
                int a = v*10+j;
                if(prime(a)) cur.push_back(a);
            }
        }
        prev=cur;
    }
    for(auto a : cur) printf("%d\n",a);
}

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

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

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

[풀이]
1. pair 배열에 {Si+1,-1}, {Ti,1} 로 분할하여 저장한 뒤 오름차순으로 정렬한다.
2. cnt 변수를 선언하고 여기에는 현재 시간에 동시에 진행중인 수업의 개수(필요한 강의실 수)가 저장되게 된다.
3. cnt 변수를 업데이트 하는 방법은 정렬된 배열 a를 0~2N-1 순서로 차례로 순회하면서
second (-1또는 1) 값을 cnt에서 빼준다. Si (시작) 일때는 새로운 강의가 추가되므로 1을 더해주고
Ti 일때는 강의가 끝나느 것이므로 1을 빼주는 것이다. 정렬할 때 Si에 -1을 넣은 것은 오름차순으로 정렬시 Si가 먼저 오게 하기 위함이다.
이런 식으로 순회하면서 cnt를 업데이트할때, cnt가 가장 큰 값이 나오는 순간이 필요한 강의실 수가 가장 많은 순간이고
필요한 최대 강의실 수가 된다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,ans;
pair<int,int> a[400001];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        int s,e;
        scanf("%d%d",&s,&e);
        a[i]={s+1,-1};
        a[i+N]={e,1};
    }
    sort(a,a+2*N);

    int cnt=0;
    for(int i=0;i<2*N;i++){
        cnt-=a[i].second;
        ans=max(cnt,ans);
    }
    printf("%d",ans);
}

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

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

[난이도] Gold5
[유형] BFS

[풀이]
1~N의 모든 회원을 시작점으로 BFS를 돌리면서 가장 먼 회원과의 거리를 구한 뒤 point[i]에 저장한다.
point[i] (i:1~N) 중 가장 적은 값을 가지고 있는 회원들이 회장 후보이다.

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int N,point[51],visit[51];
vector<int> adj[51];

int sol(int k){
    memset(visit,0,sizeof(visit));
    queue<int> q;
    visit[k]=1;
    q.push(k);
    int ret=0;
    while(!q.empty()){
        int qf = q.front(); q.pop();
        ret=max(ret,visit[qf]);
        for(int nxt : adj[qf]){
            if(!visit[nxt]){
                visit[nxt]=visit[qf]+1;
                q.push(nxt);
            }
        }
    }
    return ret;
}
int main(){
    scanf("%d",&N);
    while(1){
        int a,b;
        scanf("%d%d",&a,&b);
        if(a==-1) break;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int mv = 1e7;
    vector<int> ans;
    for(int i=1;i<=N;i++) {
        point[i]=sol(i);
        mv=min(mv,point[i]);
    }
    for(int i=1;i<=N;i++) 
        if(point[i]==mv) ans.push_back(i);

    printf("%d %d\n",mv-1,ans.size());
    for(auto a : ans) printf("%d ",a);
}

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

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

[난이도] Gold5
[유형] DP

[풀이]
dp[i][k] (i:0~N-1, k:0,1)
dp[i][0] : 숫자 한개를 제거하지 않은 i번째로 끝나는 수열의 합 중 최댓값
dp[i][1] : 숫자 한개를 제거한 i번째로 끝나는 수열의 합 중 최댓값

k=0을 구하는 법 : dp[i][0] = dp[i-1][0]<0 ? a[i] : dp[i-1][0]+a[i]
숫자를 제거하지 않을 것이므로 dp[i-1]에 a[i]를 이어붙이면 된다. 단, dp[i-1]이 음수인 경우에는
dp[i-1]을 합치는 것은 합을 줄어들게 하므로 a[i]만 dp[i][0]으로 설정한다.

k=1을 구하는 법 : dp[i][1] = max(dp[i-1][0],dp[i-1][1]+a[i]);
dp[i-1][0]은 a[i] (제일 오른쪽)을 제거하는 경우인데, 아직 숫자가 제거되지 않았어야 하므로 dp[i-1][0]이다.
dp[i-1][1]+a[i]는 이미 숫자가 제거된 dp[i-1][1]에 a[i]를 이어붙이는 케이스이다.

위의 방법으로 O(N)에 해결이 가능하다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,a[100000],dp[100000][2],ans;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    dp[0][0]=a[0];
    ans=a[0];
    for(int i=1;i<N;i++){
        dp[i][0] = dp[i-1][0]<0 ? a[i] : dp[i-1][0]+a[i];
        dp[i][1] = max(dp[i-1][0],dp[i-1][1]+a[i]); 
        ans=max(dp[i][0],ans);
        ans=max(dp[i][1],ans);
    }
    printf("%d",ans);
}

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

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

[난이도] Gold5
[유형] Queue,Multiset

[풀이]
두 개의 Queue 혹은 Multiset을 이용해 간단히 해결할 수 있다.

#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
int T,k;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&k);
        char cmd;
        int v;
        multiset<int> ms;
        while(k--){
            scanf(" %c %d",&cmd,&v);
            if(cmd=='I'){
                ms.insert(v);
            }else if(!ms.empty()){
                ms.erase(v==1? --ms.end() : ms.begin());
            }
        }
        if(ms.empty()) puts("EMPTY");
        else printf("%d %d\n",*(--ms.end()),*ms.begin());
    }
}

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

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

[난이도] Gold5
[유형] DFS

[풀이]
친구관계를 이용해 그래프를 만들어 준 뒤, 0~N-1의 모든 점에서 dfs를 돌면서 깊이가 5가 되는 경우가 있으면 1을 출력해야 한다. 일반 dfs와 다르게 dfs 함수를 return하기 전에 visit[n]=0 으로 처리를 해줘야 놓치는 케이스 없이 답을 찾을 수 있다.

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int N,M,visit[2001];
vector<int> adj[2001];
bool ok=0;
void dfs(int n,int k){
    if(ok) return;
    visit[n]=1;
    if(k==5) ok=1;
    for(auto nxt : adj[n]){
        if(!visit[nxt]) dfs(nxt,k+1);
    }
    visit[n]=0;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<M;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=0;i<N;i++){
        memset(visit,0,sizeof(visit));
        dfs(i,1);
        if(ok) break;
    }
    printf("%d",ok);
}

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