프로그래밍

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

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

[풀이]
N 제한이 5밖에 되지 않으므로 백트래킹 함수를 통해 모든 경우의 경로를 다 해보면 됩니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,dy[2]={1,0},dx[2]={0,1},minv=1e9,maxv=-1e9;
char a[5][5];
void sol(int y,int x,int val){
    if(y==N-1&&x==N-1){
        minv=min(minv,val);
        maxv=max(maxv,val);
        return;
    }
    for(int i=0;i<2;i++){
        int ny=y+dy[i],nx=x+dx[i];
        if(ny>=N||nx>=N) continue;
        int nv = val;
        if(a[y][x]=='-'){
            nv-=a[ny][nx]-'0';
        }else if(a[y][x]=='+'){
            nv+=a[ny][nx]-'0';
        }else if(a[y][x]=='*') {
            nv*=a[ny][nx]-'0';
        }
        sol(ny,nx,nv);
    }
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++) scanf(" %c",&a[i][j]);
    sol(0,0,a[0][0]-'0');
    printf("%d %d",maxv,minv);
}

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

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

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

[풀이]
핀의 개수가 최대 8개밖에 되지 않기 때문에 핀의 위치를 저장한 set, 보드의 상태를 저장한 vector를
파라미터로 하는 백트래킹 함수를 짜주면 완전탐색으로 답을 구할 수 있습니다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
int tc,dy[4]={-1,1,0,0},dx[4]={0,0,1,-1},ans,ansc;
void sol(vector<string> b,set<pair<int,int>> p,int cnt){
    if(ans>p.size()){
        ans=p.size();
        ansc=cnt;
    }else if(ans==p.size() && ansc>cnt) ansc=cnt;
    for(auto [y,x] : p){
        for(int i=0;i<4;i++){
            int ny=y+dy[i],nx=x+dx[i];
            if(ny<0||nx<0||ny>=5||nx>=9||b[ny][nx]!='o') continue;
            int nny=ny+dy[i],nnx=nx+dx[i];
            if(nny<0||nnx<0||nny>=5||nnx>=9||b[nny][nnx]!='.') continue;
            auto tb=b;
            auto tp=p; 
            tb[y][x]='.';
            tb[ny][nx]='.';
            tb[nny][nnx]='o';
            tp.insert({nny,nnx});
            tp.erase({ny,nx});
            tp.erase({y,x});
            sol(tb,tp,cnt+1);
        }
    }
}
int main(){
    cin >> tc;
    while(tc--){
        ans=9e8,ansc=9e8;
        vector<string> board;
        set<pair<int,int>> p;
        for(int i=0;i<5;i++){
            string s;
            cin >> s;
            board.push_back(s);
            for(int j=0;j<s.size();j++){
                if(s[j]=='o') p.insert({i,j});
            }
        }
        sol(board,p,0);
        cout << ans << " " << ansc << "\n";
    }
}

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

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

[난이도] Gold5
[유형] DP

[풀이]
3의 배수의 모든 자릿수의 합을 3으로 나눈 나머지는 0 이라는 성질을 알고 있어야 풀 수 있는 문제입니다.
15의 배수의 1의 자리수는 0또는 5인데 문제의 조건에 의해 1의 자리에는 5밖에 올수밖에 없습니다.
이를 만족하면서 위의 3의 배수의 성질을 만족하는 모든 수를 찾아주면 됩니다.

dp[i][j] : 자리수가 i이면서 각 자리수의 합을 3으로 나눈 나머지가 j인 수들의 개수

위와 같이 정의해주면 아래와 같은 점화식이 나옵니다.

dp[i][0]=(dp[i-1][1]+dp[i-1][2]); // (1+5)%3==0, (2+1)%3==0
dp[i][1]=(dp[i-1][2]+dp[i-1][0]); // (2+5)%3==1, (0+1)%3==1
dp[i][2]=(dp[i-1][1]+dp[i-1][0]); // (0+5)%3==2, (1+1)%3=002

최종적으로 dp[N][0]을 출력해주면 됩니다.

#include <cstdio>
int N,mod=1e9+7,dp[1600][3];
int main(){
    scanf("%d",&N);
    dp[2][0]=dp[2][1]=1;
    for(int i=3;i<=N;i++){
        dp[i][0]=(dp[i-1][1]+dp[i-1][2])%mod;
        dp[i][1]=(dp[i-1][2]+dp[i-1][0])%mod;
        dp[i][2]=(dp[i-1][1]+dp[i-1][0])%mod;
    }
    printf("%d",dp[N][0]);
}

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

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

[난이도] Gold5
[유형] 다익스트라

[풀이]
다익스트라

#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;
int N,M,dist[50001];
vector<pair<int,int>> adj[50001];
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        adj[u].push_back({v,d});
        adj[v].push_back({u,d});
    }
    for(int i=1;i<=N;i++) dist[i]=9e8;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    pq.push({0,1});
    dist[1]=0;
    while(!pq.empty()){
        auto [d,cur] = pq.top(); pq.pop();
        if(dist[cur]!=d) continue;
        for(auto [nxt,nd] : adj[cur]){
            if(dist[nxt] > d+nd){
                dist[nxt]=d+nd;
                pq.push({dist[nxt],nxt});
            }
        }
    }
    printf("%d",dist[N]);
}

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

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

[난이도] Gold5
[유형] Greedy

[풀이]
O(N)에 0~N-1을 한번씩만 확인하면서 문제를 해결할 수 있습니다.
a[h] : 현재까지 a[h]에 위치하는 화살의 개수

현재 입력으로 v가 들어왔다면 a[v+1]을 확인해서 1 이상이면 v+1 위치에 화살이 내려와서
v의 풍선을 제거할 수 있습니다.
만약 a[v+1]이 0이라면 v 위치의 풍선을 제거할 풍선이 없으므로 v 높이로 화살을 날려야 하므로
정답에 1을 추가해줍니다.

#include <cstdio>
using namespace std;
int N,ans,a[1000001];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        int v;
        scanf("%d",&v);
        if(a[v+1]){
            a[v+1]--;
            a[v]++;
        }else{
            ans++;
            a[v]++;
        }
    }
    printf("%d",ans);
}

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

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

[난이도] Gold5
[유형] BFS

[풀이]
visit[y][x][k] 배열을 이용해서 0,0부터 시작하는 BFS를 해주면 됩니다.
k==0인 경우는 검을 줍지 않은 상태라 벽을 통과 못하는 상태이고,
k==1인 경우는 검을 주워 벽을 무시할 수 있는 상태입니다.

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
int N,M,T,board[101][101],visit[101][101][2];
int dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
struct P{
    int y,x,k;
};
int main(){
    scanf("%d%d%d",&N,&M,&T);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) scanf("%d",&board[i][j]);
    queue<P> q;
    visit[0][0][0]=1;
    q.push({0,0,0});
    int cnt=0;
    while(!q.empty()){
        int sz = q.size();
        while(sz--){
            auto [y,x,k] = q.front(); q.pop();
            if(y==N-1&&x==M-1){
                printf("%d",cnt);
                return 0;
            }
            for(int i=0;i<4;i++){
                int ny=y+dy[i], nx=x+dx[i],nk=k;
                if(board[ny][nx]==2) nk=1;
                if(ny<0||nx<0||ny>=N||nx>=M||visit[ny][nx][nk]) continue;
                if(board[ny][nx]==1&&nk==0) continue;
                visit[ny][nx][nk]=1;
                q.push({ny,nx,nk});
            }
        }
        cnt++;
        if(cnt>T) break;
    }
    puts("Fail");
}

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

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

[난이도] Gold2
[유형] DP

[풀이]
최솟값은 DP, 최댓값은 규칙성을 이용

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int tc,N;
long long dp[101]={0,0,1,7,4,2,6,8,10,};
int main(){
    cin >> tc;
    for(int i=9;i<101;i++){
        dp[i]=9e20;
        for(int j=2;j<=7;j++){
            long long v = dp[i-j]*10;
            if(j!=6) v+=dp[j];
            dp[i]=min(dp[i],v);
        }
    }
    while(tc--){
        cin >> N; 
        string maxv;
        cout << dp[N];
        if(N%2==0) {
            for(int i=0;i<N/2;i++) maxv+='1';
        }
        else{
            maxv+='7';
            for(int i=0;i<N/2-1;i++) maxv+='1';
        }
        cout << ' ' << maxv << '\n';
    }
}

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

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

[난이도] Gold2
[유형] Greedy

[풀이]
문제들 중에 데드라인이 최대인 문제의 데드라인이 M일 때,
M+1시간부터는 모든 문제의 데드라인이 종료되므로 문제를 풀 수 없습니다.
결국 1,2,3...M 시간에 각각 최대 1문제를 풀 수 있고 각 시간에 컵라면을 최대로 하기에 유리한 문제를 풀어야 합니다.

Greedy 알고리즘을 이용해야 하는데
M,M-1,M-2...1 과 같이 풀어야 하는 문제를 거꾸로 구해주면 쉽게 해결이 가능합니다.

1) 각 문제를 데드라인 순서로 정렬
2) i를 M~1 순서로 순회하면서 i보다 크거나 같은 데드라인을 가진 문제들의 컵라면 수를 우선순위 큐에 push
3) i시간에 풀 수 있는 문제는 과정 2)에 의해 모두 우선순위 큐에 들어있으므로 큐의 top이 결국 i시간에 선택할 수 있는    최적의 문제이므로 컵라면의 수를 ans에 더해줌

위의 과정을 반복하면서 누적된 ans 값이 최종 정답입니다.

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int N,M;
pair<int,int> a[200000];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        scanf("%d%d",&a[i].first,&a[i].second);
        M=max(M,a[i].first);
    }
    int ans=0;
    sort(a,a+N);
    priority_queue<int> pq;
    int j=N-1;
    for(int i=M;i>=1;i--){
        for(;j>=0&&a[j].first>=i;j--) pq.push(a[j].second);
        if(!pq.empty()) {
            ans+=pq.top();
            pq.pop();
        }
    }
    printf("%d",ans);
}

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