프로그래밍

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

[난이도] Gold4
[유형] Stack

[풀이]
새로운 string ans를 만들고 앞에서부터 하나씩 넣어보면서 PPAP가 채워지면 P로 바꾸는 식으로 문제를 해결한다.
1. 'A' 다음에 'P'가 오면 'A' 앞에는 무조건 'PP'가 있으므로 'PA'를 pop해주면 'P'만 남게되어 'PPAP'를 'P'로 바꾼게 된다.
2. 현재 'A'를 넣을 차례인데 앞에 두 문자가 'PP'가 아니면 'PPAP' 문자가 아니므로 ok flag를 0으로 설정한다.
3. 최종 ans 문자가 'PPAP'이거나 'P'이면 'PPAP' 문자이다.

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

#include <iostream>
#include <string>
using namespace std;
string s;
int main(){
    cin >> s;
    bool ok = 1;
    string ans;
    for(int i=0;i<s.size();i++){
        if(s[i]=='P'){
            if(ans.empty()) ans.push_back('P');
            else if(ans.back()=='A') ans.pop_back(),ans.pop_back();
            else ans.push_back('P');
        }else{
            if(ans.size()>=2 && ans.back()=='P'&&ans[ans.size()-2]=='P') ans.push_back('A');
            else {
                ok=0;
                break;
            }
        }
    }
    if(ans=="PPAP") ans="P";
    if(!ok || ans != "P") puts("NP");
    else puts("PPAP");
}

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

[난이도] Gold4
[유형] 구현

[풀이]
터널 통과전 각 자동차에 대해 자신보다 앞에 가고 있는 자동차를 적절한 자료구조에 기록해놓고
터널 통과후 앞에 이전에 있던 차가 없으면 그 차는 추월을 한것이다.
string 자체로 기록하기 위해 map,set 등을 이용하였는데 index로 변환하여 풀면
메모리 및 시간을 줄일 수 있다.

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

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;
string a[1001];
int main(){
    ios_base::sync_with_stdio();
    cin.tie();
    map<string,vector<string>> start;
    map<string,set<string>> end;
    int N;
    cin>>N;
    for(int i=N-1;i>=0;i--) cin>>a[i];
    for(int i=0;i<N-1;i++)
        for(int j=i+1;j<N;j++) start[a[i]].push_back(a[j]);
    
    for(int i=N-1;i>=0;i--) cin>>a[i];
    for(int i=0;i<N-1;i++)
        for(int j=i+1;j<N;j++) end[a[i]].insert(a[j]);
    
    int ans = 0;
    for(auto k : start){
        string n = k.first;
        for(auto e : k.second){
            if(end[n].find(e) == end[n].end()) {
                ans++;
                break;
            }
        }
    }
    cout << ans;
}

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

[난이도] Gold4
[유형] DFS

[풀이]
DFS를 이용해서 cycle이 없는 연결요소를 찾아야 한다.
cycle을 찾는 방법은 다음과 같다.
1. DFS로 방문하는 순서를 dfs(int n,int cnt)와 같이 cnt를 한개씩 증가시키면 visit 배열에
기록해준다.
2. 인접한 노드가 cnt보다 2이상 큰수라면 이미 방문한 노드이므로 cycle이 있는것이다. (1이면 부모노드이므로 skip)
=> cycle이 없는 연결요소들의 개수가 정답이다.

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int N,M,visit[501],tc;
vector<int> adj[501];
bool ok =1;
void dfs(int n,int cnt){
    visit[n]=cnt;
    for(auto nxt : adj[n]){
        if(!visit[nxt]) dfs(nxt,cnt+1);
        else if(visit[n]-visit[nxt]>1) ok=0;
    }
}
int main(){
    while(1){
        scanf("%d%d",&N,&M);
        memset(visit,0,sizeof(visit));
        for(int i=0;i<=N;i++) adj[i].clear();
        if(N==0) break;
        while(M--){
            int u,v;
            scanf("%d%d",&u,&v);
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        int ans = 0;
        for(int i=1;i<=N;i++){
            if(!visit[i]){
                ok=1;
                dfs(i,0);
                ans+=ok;
            }
        }
        printf("Case %d: ",++tc);
        if(ans==0) puts("No trees.");
        else if(ans==1) puts("There is one tree.");
        else printf("A forest of %d trees.\n",ans);
    }
}

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

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

[난이도] Gold4
[유형] BFS

[풀이]
visit[N][M][k] (k= 지팡이 사용횟수) 배열을 선언해서 현재 지팡이 사용횟수를 저장하는
방식으로 BFS를 돌려주면 된다.

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

#include <cstdio>
#include <queue>
using namespace std;
struct P{int y,x,k;};
int map[1000][1000],N,M,hy,hx,ey,ex,dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
int visit[1000][1000][2];
int main(){
    scanf("%d%d%d%d%d%d",&N,&M,&hy,&hx,&ey,&ex);
    hy--,hx--,ey--,ex--;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) scanf("%d",&map[i][j]);
    
    queue<P> q;
    visit[hy][hx][0]=1;
    q.push({hy,hx,0});
    int cnt = 0;
    while(!q.empty()){
        int qsz = q.size();
        while(qsz--){
            auto f = q.front(); q.pop();
            if(f.y==ey && f.x==ex){
                printf("%d",cnt);
                return 0;
            }
            for(int i=0;i<4;i++){
                int ny = f.y+dy[i];
                int nx = f.x+dx[i];
                if(ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
                if(map[ny][nx]){
                    if(!f.k && !visit[ny][nx][1]) {
                        visit[ny][nx][1]=1;
                        q.push({ny,nx,1});
                    }
                }else if(!visit[ny][nx][f.k]){
                    visit[ny][nx][f.k]=1;
                    q.push({ny,nx,f.k});
                }
            }
        }
        cnt++;
    }
    puts("");
}

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

[난이도] Gold4
[유형] DP

[풀이]
구조체를 선언해서 index,넓이,높이,무게를 저장한 뒤 넓이의 내림차순으로 정렬한다.
그 뒤에 무게를 기준으로 LIS DP를 적용해서 최적의 케이스를 구해주면 된다.

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

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct P{
    int idx,width,height,weight;
};
int N,dp[101],par[101];
P a[101];
bool cmp(P& u,P& v){
    if(u.width > v.width) return 1;
    else if(u.width == v.width) return u.weight > v.weight;
    return 0;
}
int sol(int n){
    int& ret = dp[n];
    if(ret !=-1) return ret;
    ret = a[n].height;
    for(int i=n+1;i<=N;i++){
        if(a[n].weight > a[i].weight && ret < a[n].height+sol(i)) {
            ret = a[n].height+sol(i);
            par[n]=i;
        }
    }
    return ret;
}
void prt(int n,int cnt){
    if(n==0) {
        printf("%d\n",cnt);
        return;
    }
    prt(par[n],cnt+1);
    printf("%d\n",a[n].idx);
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) {
        scanf("%d%d%d",&a[i].width,&a[i].height,&a[i].weight);
        a[i].idx=i;
    }
    sort(a+1,a+1+N,cmp);
    memset(dp,-1,sizeof(dp));

    a[0].weight=9e8;
    sol(0);
    prt(par[0],0);
}

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

[난이도] Gold4
[유형] ad hoc

[풀이]
안풀려서 다른 사람의 풀이를 참고하였다.
ad hoc 문제라고 한다. bfs,dfs,dp 등 정형화된 문제유형이 아닌 해당 문제에만
특화된 풀이법으로 풀어야 하는 문제라고 한다. (창의적으로..)

이 문제는 배열 a[i]=i (i:1~N) 으로 설정해놓고
(u,v) 쌍에 대해 a[u]++,a[v]-- 를 해주면 답이 나온다.

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

#include <cstdio>
int N,M,a[100001],exist[100001];
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++) a[i]=i;
    while(M--){
        int u,v;
        scanf("%d%d",&u,&v);
        a[u]++,a[v]--;
    }
    for(int i=1;i<=N;i++) {
        if(exist[a[i]]){
            puts("-1");
            return 0;
        }
        exist[a[i]]=1;
    }
    for(int i=1;i<=N;i++) printf("%d ",a[i]);
}

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

[난이도] Gold4
[유형] 플로이드 와샬

[풀이]
플로이드 와샬로 모든 지점간 거리를 구한 후
각 점에서 M거리 이하인 지점의 아이템 개수를 모두 더한 값의 최솟값이 정답이다.

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

#include <cstdio>
#include <algorithm>
using namespace std;
int N,M,R,item[101],dist[101][101],inf=9e8,ans;
int main(){
    scanf("%d%d%d",&N,&M,&R);
    for(int i=1;i<=N;i++) scanf("%d",&item[i]);
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(i!=j) dist[i][j] = inf;
        }
    }
    while(R--){
        int a,b,l;
        scanf("%d%d%d",&a,&b,&l);
        dist[a][b] = min(dist[a][b],l);
        dist[b][a] = min(dist[b][a],l);
    }

    for(int k=1;k<=N;k++)
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++) dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);

    for(int i=1;i<=N;i++){
        int sum=0;
        for(int j=1;j<=N;j++){
            if(dist[i][j]<=M) sum+=item[j];
        }
        ans = max(ans,sum);
    }
    printf("%d",ans);
}

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

[난이도] Gold4
[유형] BFS

[풀이]
visit배열의 값을 3가지로 사용한다. (0:불도 안켜진 상태 1:불만 켜진상태 2:방문완료한 상태)
(1,1)부터 BFS를 시작한다. 인접하고 불이 켜진 곳을 queue에 넣기 전에
현재 위치에서 킬 수 있는 불을 켜준다.
여기서 주의할 점이 방금 불을 켠 점의 인접한 곳에 (2:방문 완료한 상태)인 점이 있다면 이곳도
방문할 수 있는 점에 추가되어야 하기 때문에 queue에 넣어줘야 한다.

#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
int N,M,cnt,visit[102][102],dy[4]={-1,1,0,0},dx[4]={0,0,1,-1}; 
vector<pair<int,int>> adj[101][101];
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int y,x,b,a;
        scanf("%d%d%d%d",&x,&y,&a,&b);
        adj[y][x].push_back({b,a});
    }
    queue<pair<int,int>> q;
    q.push({1,1});
    visit[1][1]=2;
    int cnt=1;
    while(!q.empty()){
        int qsz=q.size();
        auto f = q.front(); q.pop();
        int y = f.first, x=f.second;
        for(auto p : adj[y][x]){
            int ny = p.first, nx = p.second;
            if(!visit[ny][nx]){
                for(int i=0;i<4;i++){
                    int ty=ny+dy[i],tx=nx+dx[i];
                    if(visit[ty][tx]==2) {
                        q.push({ty,tx});
                        break;
                    }
                }
                visit[ny][nx]=1;
                cnt++;
            }
        }
        for(int i=0;i<4;i++){
            int ny = y+dy[i], nx= x+dx[i];
            if(visit[ny][nx]==1){
                visit[ny][nx]=2;
                q.push({ny,nx});
            }
        }
    }
    printf("%d",cnt);
}

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