프로그래밍

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

[난이도] Gold4
[유형] DP,Bitmask,완전탐색

[풀이]
next_permutation으로 푸니까 TLE로 틀려서 Bitmask DP로 풀었다.
선수 11명, 포지션 11개밖에 안되므로 DP[11][1<11] 배열로
11x2^11 O(22528) 안에 해결이 가능하다.

next_permutation이 아닌 재귀를 활용한 완전탐색으로도 0인 경우에 가지치기를 해주면
시간내에 해결이 가능하다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int tc,a[11][11],dp[11][1<<11],inf=-9e8;
int sol(int n,int msk){
    if(n==11) return 0;
    int& ret = dp[n][msk];
    if(ret!=-1) return ret;
    ret = inf;
    for(int i=0;i<11;i++){
        if(((1<<i)&msk)==0 && a[i][n]){
            ret = max(ret,sol(n+1,msk|(1<<i))+a[i][n]);
        }
    }
    return ret;
}
int main(){ 
    scanf("%d",&tc);
    while(tc--){
        for(int i=0;i<11;i++)
            for(int j=0;j<11;j++) scanf("%d",&a[i][j]);       
        memset(dp,-1,sizeof(dp));
        printf("%d\n",sol(0,0));
    }
}

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

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

[난이도] Gold4
[유형] BFS

[풀이]
BFS를 이용해 풀 수 있다.
각 문,거울에 번호를 준 뒤, 문,거울간에 인접행렬을 만들어서 풀수도 있지만
본인은 맵에서 한칸씩 움직이는 방식으로 풀었다.
메모제이션 배열은 visit[50][50][2]과 같이 선언해야 한다.
visit[y][x][0] -> 세로 방향에서 y,x에 도착한 경우.
visit[y][x][1] -> 가롱 방향에서 y,x에 도착한 경우.

두 방향으로 구분한 이유는 y,x에 거울을 설치할 수 있을 때,
세로 방향에서 왔을 때 거울을 설치하면 다음 방향으로 가로방향(좌,우)로 이동이 가능하고
가로 방향에서 왔으면 세로방향으로의 이동이 가능해지기 때문이다.
만약 visit[50][50]으로만 해놓고 풀면 방향전환을 할 수 없는 경우가 생기게 된다.

큐에는 {y,x,d,k}를 넣어준다. d는 현재 움직이고 있는 방향이고, k는 현재까지 사용한 거울 개수이다.
만약 '.'인 칸이면 그냥 d방향으로만 전진하고 거울설치가 가능한 '!' 칸이면 좌우로 방향이 바뀌는 경우도
k+1을 해주고 추가로 큐에 넣어주면 된다.

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int dy[4]={1,0,-1,0};
int dx[4]={0,1,0,-1};
int N,visit[50][50][2],sy=-1,sx,ey,ex;
char map[50][50];
struct P{
    int y,x,d,k;
};
int main(){ 
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            scanf(" %c",&map[i][j]);
            if(map[i][j]=='#') {
                if(sy==-1)sy=i,sx=j;
                else ey=i,ex=j;
            }
        }
    }
    memset(visit,-1,sizeof(visit));
    queue<P> q;
    for(int i=0;i<4;i++) {
        q.push({sy,sx,i,0});
        visit[sy][sx][i%2]=0;
    }
    while(!q.empty()){

        P f = q.front(); q.pop();
        int ny = f.y+dy[f.d], nx = f.x+dx[f.d];
        if(ny < 0 || nx < 0 || ny >= N || nx >= N || map[ny][nx]=='*') continue;
        
        if(visit[ny][nx][f.d%2]==-1 || visit[ny][nx][f.d%2] > f.k) {
            visit[ny][nx][f.d%2] = f.k;
            q.push({ny,nx,f.d,f.k});
        }        
        if(map[ny][nx]=='!'){
            if(visit[ny][nx][(f.d+1)%2]==-1 || visit[ny][nx][(f.d+1)%2] > f.k+1) {
                visit[ny][nx][(f.d+1)%2] = f.k+1;
                q.push({ny,nx,(f.d+1)%2,f.k+1});
                q.push({ny,nx,2+(f.d+1)%2,f.k+1});
            }            
        }
    }
    int ans = 9e8;
    if(visit[ey][ex][1]!=-1) ans = min(ans,visit[ey][ex][1]);
    if(visit[ey][ex][0]!=-1) ans = min(ans,visit[ey][ex][0]);
    printf("%d",ans);
}

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

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

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

[풀이]
어떤 건물 i에서 j를 볼 수 있으려면 i+1~j-1 인 어떤 모든 k에 대해
i,j의 기울기가 i,k의 기울기보다 커야한다.
i,j를 볼 수 있다는 것은 j에서도 i를 볼 수 있다는 것이다.
2중 for문으로 모든 i,j 짝에 대해 볼 수 있는지 확인할 수 있다.

#include <cstdio>
int N,a[50],ans,c[50];
double getD(int i,int j){
    return (a[j]-a[i])/(double)(j-i);
}
int main(){ 
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    for(int i=0;i<N-1;i++){
        double cur,d;
        for(int j=i+1;j<N;j++){
            d = getD(i,j);
            if(j-1==i || cur < d){
                cur = d;
                c[i]++; c[j]++;
            }
        }
    }
    for(int i=0;i<N;i++) if(ans < c[i]) ans=c[i];
    printf("%d",ans);
}

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

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

[난이도] Gold4
[유형] Map, Trie

[풀이]
종의 이름을 key로 하는 (string,int) pair의 map을 만들어서
해당 종의 총 갯수를 구하면 된다.

나무 이름에 공백이 있을 수도 있으므로 한줄 전체를 입력으로 받아야 한다.
getline(cin,s) 함수를 이용하면 한줄을 단위로 입력받을 수 있다.
EOF 같은 경우 아래와 같이 처리해주면 파일이 끝날 때 while문을 빠져나가게 된다.
while(getline(cin,s)){

}

Trie로 풀면 더 빠른시간내에 해결할 수 있다고 한다.

#include <iostream>
#include <map>
#include <string>
#include <cmath>
using namespace std;
map<string,int> m;
int n;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    while(getline(cin,s)){
        m[s]++;
        n++;
    }
    for(auto k : m){
        double b = 100*k.second / (double)n;
        printf("%s %.4lf\n",k.first.c_str(),b);
    }
}

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

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

[난이도] Gold4
[유형] 재귀

[풀이]
재귀함수를 이용해 left와 right 자식의 높이를 비교해서 낮은 쪽이 높은 쪽과 같아지도록 수정한다.

#include <cstdio>
int k,last,a[1<<21];
long long ans;
int sol(int n){
    if((1<<k)-1 <= n && n < last) return 0;
    int l = sol(n*2+1),r = sol(n*2+2);
    if(a[n*2+1]+l<a[n*2+2]+r) a[n*2+1] = a[n*2+2]+r-l;
    else a[n*2+2] = a[n*2+1]+l-r;
    ans += a[n*2+2]+a[n*2+1];
    return l+a[n*2+1];
}
int main(){
    scanf("%d",&k);
    last = (1<<(k+1))-1;
    for(int i=1;i<last;i++) scanf("%d",&a[i]);
    sol(0);
    printf("%lld",ans);
}

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

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

[난이도] Gold4
[유형] DFS

[풀이]
무방향 그래프의 cycle을 찾는 문제이다.
next node가 이미 방문한 node이면서 부모가 아니면 cycle이다.
부모를 체크하기 위해 visit 배열에 방문한 순서를 저장해놓고
현재 노드의 visit, 다음 노드의 visit 차가 1이면 부모 노드이므로 무시한다.

#include <cstdio>
int N,M,dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
char map[50][50];
int visit[50][50];
bool dfs(int y,int x,int k){
    visit[y][x]=k;
    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 || map[ny][nx]!=map[y][x]) continue; 
        if(visit[ny][nx]){
            if(k-visit[ny][nx]>1) return 1;
        } else if(dfs(ny,nx,k+1)) return 1;
    }
    return 0;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) scanf(" %c",&map[i][j]);  
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(!visit[i][j]){
                if(dfs(i,j,0)){
                    puts("Yes");
                    return 0;
                }
            }
        }
    }
    puts("No");
}

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

www.acmicpc.net/problem/10986

[난이도] Gold4
[유형] 누적합

[풀이]
(i,j) 구간합이 M으로 나누어 떨어지는 경우는
sum(1,j)%M == sum(1,i-1)%M 인 경우이다.

a[1]+a[2]...a[i-1]+a[i]+a[i+1]....a[j]

왜냐하면 j까지의 합이 위와 같고

만약 sum(1,i-1)%M가 k 일때, sum(1,j)%M도 k이려면
sum(i,j)%M은 0이어야 한다.

결국 정답은 나머지가 똑같은 누적합 중에서 두개를 뽑는 경우의 수이다.

#include 
int N,M,cnt[1001],sum[1000001];
long long ans;
int main(){
    scanf("%d%d",&N,&M);
    cnt[0]++;
    for(int i=1;i<=N;i++) {
        int v;
        scanf("%d",&v);
        sum[i] = (sum[i-1]+v)%M;
        cnt[sum[i]]++;
    } 
    for(int i=0;i<m;i++){ class="hljs-keyword" <span="">int n = cnt[i];
        if(n>1) ans+= ((long long)n*(n-1))/2;
    }
    printf("%lld",ans);
}</m;i++){>

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

www.acmicpc.net/problem/2643  

[난이도] Gold4

[유형] DP

[풀이]

2차원 LIS 문제이다.

정렬 이후 DP로 해결할 수 있다.

점화식 :

dp[n] = max(dp[i]); (n+1 <= i <= N)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct P{
    int u,v;
};
int N,dp[101];
P a[101];
bool cmp(P& a,P& b){
    if(a.u > b.u) return 1;
    else if(a.u==b.u) return a.v > b.v;
    return 0;
}
int sol(int n){
    int& ret = dp[n];
    if(ret!=-1) return ret;
    ret = 0;
    for(int i=n+1;i<=N;i++) if(a[i].v <= a[n].v) ret = max(ret,sol(i));
    return ret += 1;
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(u<v) swap(u,v);
        a[i].u=u, a[i].v=v;
    }
    a[0].u=a[0].v=9e8;
    sort(a,a+N+1,cmp);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0)-1);
}

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