프로그래밍

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

[난이도] Gold2
[유형] DP

[풀이]
DP[y][x] : y,x에서 출발해서 미로에서 탈출 가능하면 1, 아니면 0

#include <cstdio>
#include <cstring>
using namespace std;
int N,M,ans,visit[501][501],dp[501][501],board[501][501],dy[4]={-1,0,1,0},dx[4]={0,1,0,-1};
int sol(int y,int x){
    visit[y][x]=1;
    int& ret =dp[y][x];
    if(ret!=-1) {
        visit[y][x]=0;
        return ret;
    }
    int d = board[y][x];
    int ny=y+dy[d],nx=x+dx[d];
    if(ny<0||nx<0||ny>=N||nx>=M) ret=1;
    else {
        if(visit[ny][nx]) ret=0;
        else ret = sol(ny,nx);
    }
    visit[y][x]=0;
    return ret; 
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++){
            char d;
            scanf(" %c",&d);
            if(d=='R') board[i][j]=1;
            else if(d=='D') board[i][j]=2;
            else if(d=='L') board[i][j]=3;
        }
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) {
            ans+=sol(i,j);
        }
    printf("%d",ans);
}

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

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

[난이도] Gold2
[유형] DP

[풀이]
트리 DP로 해결할 수 있는 문제입니다.
3차원 DP로 풀었습니다.
DP[n][p][c] : 현재 n번 마을, 부모 마을의 우수마을여부가 p, n번 마을의 우수마을 여부가 c 일때의 최댓값
              (1인 경우 우수마을, 0인 경우 일반마을)

c==1 인 경우 n의 인접한 자식 마을들은 무조건 우수마을이 될 수 없으므로
   sol(nxt,c,0) (nxt는 n의 자식 마을) 값들을 더해주면 됩니다.

c==0 인 경우 부모 마을의 우수마을여부 p를 따져봐야 합니다.
   i) p==1 (부모가 우수마을인 경우)
     이 경우에는 n의 자식은들은 인접한 마을인 n이 우수마을인 것이 보장되기 때문에
     우수마을이든 일반 마을이든 상관이 없습니다.
     그러므로 max(sol(nxt,0,0),sol(nxt,0,1)) 과 같이 우수마을,일반마을로 선택한 경우중 최댓값을 더해주면 됩니다.

   ii) p==2 (부무가 일반마을인 경우)
     n이 일반마을이고, n의 부모도 일반 마을인 경우 입니다.
     이 경우 n의 자식들 중에 반드시 한 마을은 우수 마을이어야 합니다.
     n의 자식 nxt들 중 한 마을은 무조건 우수 마을로 결정한 모든 경우를 고려서해서
     그 중 최댓값을 더해주면 됩니다.

3차원 dp 풀이

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int N,a[10001],dp[10001][2][2],visit[10001];
vector<int> tmp[10001],adj[10001];
int sol(int n,int p,int c){
    int& ret = dp[n][p][c];
    if(ret!=-1) return ret;
    ret=0;
    if(c==1){
        ret=a[n];
        for(auto nxt : adj[n]) ret+=sol(nxt,1,0);
    }else{
        if(p==1){
            for(auto nxt :adj[n]) ret+=max(sol(nxt,0,0),sol(nxt,0,1));
        }else{
            vector<int> v;
            int t=0;
            for(auto nxt :adj[n]) {
                int j = max(sol(nxt,0,0),sol(nxt,0,1));
                t+=j;
                v.push_back(j);
            }
            int mv=0;
            for(int i=0;i<adj[n].size();i++){
                int tt=t;
                tt-=v[i];
                tt+=sol(adj[n][i],0,1);
                mv=max(tt,mv);
            }
            ret=mv;
        }
    }
    return ret;
}
void tree(int n){
    visit[n]=1;
    for(auto nxt : tmp[n]){
        if(!visit[nxt]) {
            adj[n].push_back(nxt);
            tree(nxt);
        }
    }
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&a[i]);
    for(int i=0;i<N-1;i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        tmp[u].push_back(v);
        tmp[v].push_back(u);
    }
    tree(1);
    memset(dp,-1,sizeof(dp));
    printf("%d",max(sol(1,0,0),sol(1,0,1)));
}

3번 조건에 의해 부모의 우수마을 여부도 알고 있어야 하기 때문에 위와 같이 3차원 DP로 풀었는데
다른 분들의 풀이를 보고 알았는데
3번 조건은 무시해도 되는 조건이라 2차원 dp로도 해결이 가능합니다.
우리가 우려하는 아래와 같이 일반마을이 세번 연속 나오는
트리 모양은 절대로 정답이 될 수 없기 때문입니다.
점화식이 max를 구하는 방식으로 되어 있기 때문에 2번 노드를 우수마을로 선택한 경우가 정답의 후보가 될수밖에 없습니다.
   1(0)
   2(0)
 3(0) 4(0)
 1(1) 1(1)

2차원 dp 풀이

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int N,a[10001],dp[10001][2];
vector<int> adj[10001];
int sol(int n,int k,int p){
    int& ret = dp[n][k];
    if(ret!=-1) return ret;
    ret=0;
    if(k==1) ret=a[n];
    for(auto nxt : adj[n]){
        if(nxt!=p){
            if(k==0) ret+=max(sol(nxt,0,n),sol(nxt,1,n));
            else ret+=sol(nxt,0,n);
        }
    }
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&a[i]);
    for(int i=0;i<N-1;i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    adj[0].push_back(1);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0,0,0));
}

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

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

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

[풀이]
구현능력을 보는 시뮬레이션 문제입니다.
풀이법이랄게 딱히 없으며 주어진 조건에 맞게 구현해주면 됩니다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,K,board[14][14];
int dy[4]={0,0,-1,1};
int dx[4]={1,-1,0,0};
struct P{
    int num,d;
};
pair<int,int> pos[11];
vector<P> horse[14][14];
int cd(int d){
    return d%2==0 ? d+1 : d-1;
} 
bool move(int c,int y,int x,vector<P> v,int d){
    v[0].d=d;
    if(c==1) reverse(v.begin(),v.end());
    for(auto p : v) {
        horse[y][x].push_back(p);
        pos[p.num]={y,x};
    }
    return (int)horse[y][x].size()>=4;
}
int main(){
    scanf("%d%d",&N,&K);
    for(int i=0;i<=N+1;i++){
        for(int j=0;j<=N+1;j++) {
            if(i==N+1||j==N+1||i==0||j==0) board[i][j]=2;
            else scanf("%d",&board[i][j]);
        }
    }
    for(int i=1;i<=K;i++){
        int y,x,d;
        scanf("%d%d%d",&y,&x,&d);
        horse[y][x].push_back({i,d-1});
        pos[i]={y,x};
    }
    for(int ans=1;ans<=1000;ans++){
        for(int k=1;k<=K;k++){
            auto [y,x] = pos[k];
            int d,idx;
            vector<P> tmp;
            for(int i=0;i<horse[y][x].size();i++){
                if(horse[y][x][i].num==k){
                    idx=i;
                    d=horse[y][x][i].d;
                    break;
                }
            }
            for(int i=idx;i<horse[y][x].size();i++) tmp.push_back(horse[y][x][i]);
            horse[y][x].erase(horse[y][x].begin()+idx,horse[y][x].end());

            int ny=y+dy[d],nx=x+dx[d];
            bool ret=0;
            if(board[ny][nx]==2) {
                d=cd(d);
                int nny=y+dy[d],nnx=x+dx[d];   
                if(board[nny][nnx]==2) ret=move(0,y,x,tmp,d);
                else ret=move(board[nny][nnx],nny,nnx,tmp,d);

            }else{
                ret=move(board[ny][nx],ny,nx,tmp,d);
            }
            if(ret) {
                printf("%d",ans);
                return 0;
            }
        }
    }
    puts("-1");
}

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

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

[난이도] Gold3
[유형] DP

[풀이]
['abb' 의 부분수열은 {'a'}, {'b'}, {'b'}, {'ab'}, {'ab'}, {'bb'}, {'abb'}]
지문의 위 부분을 잘 봐야 합니다. 'ab'가 두번 나오기 때문에 부분수열은 연속된 수들이 아니어도 됩니다.

연속이 아니어도 아래와 같은 점화식의 DP로 해결이 가능합니다.
DP[l][r] = DP[l+1][r]+DP[l][r-1]-DP[l+1][r-1] (s[l]!=s[r])
           DP[l+1][r]+DP[l][r-1]+1 (s[l]==s[r])

s[l]!=s[r] 일때 DP[l+1][r-1]을 빼주는 이유는 DP[l+1][r],DP[l][r-1] 에 모두 DP[l+1][r-1]가
포함되어 있기 때문에 중복되지 않도록 빼주는 것입니다.

반면 s[l]==s[r] 일 때는 양 끝에 s[l],s[r]을 붙임으로써 DP[l+1][r-1]만큼이 그대로 더해지므로
빼지 않아도 되며, 부분수열 {s[l],s[r]}인 경우를 추가해야 하므로 1을 더해주었습니다.

#include <string>
#include <iostream>
#include <cstring>
using namespace std;
string s;
int dp[31][31];
int sol(int l,int r){
    if(l==r) return 1;
    if(l>r) return 0;
    int& ret=dp[l][r];
    if(ret!=-1) return ret;
    ret = sol(l+1,r)+sol(l,r-1);
    if(s[l]!=s[r]) ret-=sol(l+1,r-1); 
    else ret++;
    return ret; 
}
int main(){
    cin >> s;
    memset(dp,-1,sizeof(dp));
    cout << sol(0,s.size()-1);
}

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

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

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

[풀이]
N이 17밖에 되지 않기 때문에 백트래킹 함수의 인자로 비트마스크를 전달해서
현재 연극에 몇번 사람이 참여하고 있는지 체크할 수 있고, 비트연산을 이용해
한명씩 추가하거나 뺄 수 있습니다.
visit 배열을 선언하여 체크한 비트마스크는 체크를 해서 중복해서 방문하지 않도록 해줍니다.

#include <cstdio>
#include <vector>
using namespace std;
int N,visit[1000000],ansn;
vector<int> cur,ans;
void sol(int n,int m){
    if(n!=0&&m==0&&n>ansn){
        ansn=n;
        ans=cur;
        return;
    }
    for(int i=0;i<N;i++){
        if(((1<<i)&m)>0){
            int k=(~(1<<i))&m;
            if((n!=0&&k==0)||!visit[k]){
                visit[k]=1;
                cur.push_back(i);
                sol(n+1,k);
                cur.pop_back();
            }
        }
        if(((1<<i)&m)==0){
            int k=(1<<i)|m;
            if(!visit[k]){
                visit[k]=1;
                cur.push_back(i);
                sol(n+1,k);
                cur.pop_back();
            }
        }
    }
}
int main(){
    scanf("%d",&N);
    sol(0,0);
    printf("%d\n",ansn-1);
    for(auto a : ans) printf("%d ",a+1);
}

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

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

[난이도] Gold3
[유형] 투 포인터

[풀이]
a[i],a[i+1],a[i+2],..,a[j] 까지 같은 수가 여러번 나타나지 않을 때, a[i]를 반드시 선택하면 총 j-i+1개의 경우의 수가 있습니다.
만약 a[i+1]를 반드시 선택하면 a[i+1]~a[j] 까지 j-1개의 경우의 수가 확보가 되고, a[i]를 선택하지 않았기 때문에
a[j+1]부터 수열에 이미 포함된 나올때까지 j의 범위를 넓혀갈 수 있습니다.
위의 성질을 이용해 set에 수열에 포함된 숫자들을 저장해가며 i를 left, j를 right로 하는 투포인터를 구현해주면 됩니다.

#include <cstdio>
#include <set>
using namespace std;
using ll = long long;
int N,a[100001];
ll ans;
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&a[i]);
    int j=1;
    set<int> st={a[1]};
    for(int i=1;i<=N;i++){
        ans+=st.size();
        for(int k=j+1;k<=N+1;k++){
            if(k==N+1) {
                j=N+1;
                break;
            }
            if(st.find(a[k])!=st.end()) {
                j=k-1;
                break;
            }
            st.insert(a[k]);
            ans++;
        }
        st.erase(a[i]);
    }
    printf("%lld",ans);
}

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

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

[난이도] Gold3
[유형] MST

[풀이]
최소 스패닝 트리를 구성해주면 됩니다.

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
struct P{ int u,v,d; };
int N,M,t,uf[10001];
vector<P> a;
bool cmp(P& l,P& r){ return l.d < r.d; }
int find(int n){
    if(n==uf[n]) return n;
    return find(uf[n]);
}
bool merge(int u,int v){
    u=find(u);
    v=find(v);
    if(u==v) return 0;
    uf[u]=v;
    return 1;
} 
int main(){
    scanf("%d%d%d",&N,&M,&t);
    while(M--){
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        a.push_back({u,v,d});
    }
    sort(a.begin(),a.end(),cmp);
    for(int i=1;i<=N;i++) uf[i]=i;
    int ans=0,ct=0,j=0;
    for(int i=0;i<a.size();i++){
        auto [u,v,d] = a[i];
        if(merge(u,v)){
            ans+=d+ct;
            ct+=t;
            if(++j==N-1) break;
        }
    }
    printf("%d",ans);
}

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

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

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

[풀이]
주사위가 동서남북 방향으로 움직일 때, 각각 주사위 면의 원소들이 어떻게 이동하게 되는지를
미리 함수에 정의해고 조건에 맞게 시뮬레이션을 해주면 됩니다.

#include <cstdio>
#include <cstring>
using namespace std;
int N,M,K,board[22][22],dice[7]={0,1,2,3,4,5,6},visit[22][22];
int dy[4]={0,1,0,-1};
int dx[4]={1,0,-1,0};
void move(int d){
    int tmp[7];
    for(int i=1;i<=6;i++) tmp[i]=dice[i];
    if(d==0){
        dice[1]=tmp[4];
        dice[3]=tmp[1];
        dice[4]=tmp[6];
        dice[6]=tmp[3];
    }else if(d==1){
        dice[1]=tmp[2];
        dice[2]=tmp[6];
        dice[5]=tmp[1];
        dice[6]=tmp[5];
    }else if(d==2){ 
        dice[1]=tmp[3];
        dice[4]=tmp[1];
        dice[3]=tmp[6];
        dice[6]=tmp[4];
    }else{
        dice[1]=tmp[5];
        dice[2]=tmp[1];
        dice[5]=tmp[6];
        dice[6]=tmp[2];
    }
}
int dfs(int y,int x){
    visit[y][x]=1;
    int ret=1;
    for(int i=0;i<4;i++){
        int ny=y+dy[i],nx=x+dx[i];
        if(board[ny][nx] && board[ny][nx]==board[y][x] && !visit[ny][nx]){
            ret+=dfs(ny,nx);
        }
    }
    return ret;
}
int main(){
    scanf("%d%d%d",&N,&M,&K);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++) scanf("%d",&board[i][j]);
    int d=0,cy=1,cx=1,ans=0,cnt=0;;
    while(K--){
        int ny=cy+dy[d],nx=cx+dx[d];
        if(!board[ny][nx]){
            d=(d+2)%4;
            K++;
            continue;
        }
        move(d);
        if(dice[6]>board[ny][nx]) d=(d+1)%4;
        else if(dice[6]<board[ny][nx]) d=(d+3)%4;
        ans+=dfs(ny,nx)*board[ny][nx];
        memset(visit,0,sizeof(visit));
        cy=ny,cx=nx;
    }
    printf("%d",ans);
}

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