프로그래밍

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

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

[풀이]
현재 값에 숫자를 한개만 사용해서 더하거나 빼주는 경우,
두개를 합쳐서 더하거나 빼주는 경우를 모두 해주는 백트래킹 함수를 작성하면 됩니다.
식을 출력해야 하기 때문에 전체 식을 함수의 인자로 전달하면서
정답인 경우에는 vector에 저장해줍니다.
오름차순으로 출력하려면  vector를 정렬해주기만 하면 됩니다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int tc,N;
vector<string> ans;
void sol(int n,int v,string str){
    if(n==N+1) {
        if(v==0) ans.push_back(str.substr(1));
        return;
    }
    sol(n+1,v+n,str+"+"+to_string(n));
    if(n<=N-1) sol(n+2,v+10*n+n+1,str+"+"+to_string(n)+" "+to_string(n+1));

    if(n==1) return;

    sol(n+1,v-n,str+"-"+to_string(n));
    if(n<=N-1) sol(n+2,v-(10*n+n+1),str+"-"+to_string(n)+" "+to_string(n+1));
}
int main(){
    cin >> tc;
    while(tc--){
        cin >> N;
        sol(1,0,"");
        sort(ans.begin(),ans.end());
        for(auto a : ans) cout << a << '\n';
        cout << '\n';
        ans.clear();
    }
}

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

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

[난이도] Gold5
[유형] DP

[풀이]
정규표현식을 이용하면 간단히 해결할 수 있지만 평소 사용하지 않던 문법이라
다이나믹 프로그래밍을 이용하여 해결했습니다.

top-down DP를 이용하였습니다
dp[n] : 부분 문자열 s[n..s.size()-1] 이 SUBMARINE이면 1, NOISE이면 0을 return

s[n..n+1] 이 "01"인 경우와
s[n..n+2] 이 "100"인 경우로 나누어서 해결해주면 됩니다.

"01"인 경우 한가지 케이스밖에 없으므로 sol(n+2)를 호출하여 0인지 1인지 확인해주면 됩니다.

"100"인 경우 10001...,100001... 와 같은 케이스가 가능하므로 1이 언제 처음 등장하는지 체크해 준 뒤
만약 '1'이 i부터 등장한다면 i부터 1이 등장할 때까지 sol(i+1),sol(i+2),sol(i+3)...을 '0'이 등장하기 전까지
계속 호출해주며 return 값이 1이 나온다면 정답이므로 종료해줍니다.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
string s;
int dp[151];
int sol(int n){
    if(n==s.size()) return 1;
    int& ret = dp[n];
    if(ret!=-1) return ret;

    if(n>=s.size()-1) return ret=0;
    string t = s.substr(n,2);

    if(t=="01" && sol(n+2)) return ret=1;
    if(n>=s.size()-3) return ret=0;
    t = s.substr(n,3);

    if(t=="100"){
        int i;
        for(i=n+3;i<s.size();i++){
            if(s[i]=='1') break;
        }
        for(int j=i;j<s.size();j++){
            if(s[j]!='1') break;
            else if(sol(j+1)) return ret=1;
        }
    }
    return ret=0;
}
int main(){
    cin >> s;
    memset(dp,-1,sizeof(dp));
    if(sol(0)) cout << "SUBMARINE";
    else cout << "NOISE";
}

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

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

[난이도] Gold5
[유형] DFS

[풀이]
N개의 점에서 모두 DFS를 해주며 dist[i][j] 배열에 i,j의 유사도를 저장해줍니다.
i와 j를 연결하는 경로는 한개씩밖에 없는 트리 구조의 그래프이기 때문에 재귀함수를 이용해
간단히 유사도를 구할 수 있습니다.
이때의 시간복잡도는 O(N*N) 입니다.

유사도를 모두 구해놨으므로 각 Q개의 쿼리에 대해 O(N)에 대응할 수 있으므로 이때의 시간복잡도는
O(N*Q) 입니다.

O(N*N)과 O(N*Q) 모두 O(5000*5000)으로 넉넉하지는 않지만 시간내에 해결이 가능합니다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,Q,dist[5001][5001];
vector<pair<int,int>> adj[5001];
bool visit[5001];
void dfs(int s,int prev,int cur,int v){
    for(auto [nxt,d] : adj[cur]){
        if(nxt!=prev){
            int t = min(v,d);
            dist[s][nxt]=t;
            dfs(s,cur,nxt,t);
        }
    }
}
int main(){
    scanf("%d%d",&N,&Q);
    for(int i=0;i<N-1;i++){
        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++){
        dfs(i,-1,i,2e9);
    }
    while(Q--){
        int k,v,cnt=0;
        scanf("%d%d",&k,&v);
        for(int i=1;i<=N;i++){
            if(dist[i][v] >= k) cnt++;
        }
        printf("%d\n",cnt);
    }
}

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

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

[난이도] Gold5
[유형] BFS

[풀이]
*,+,-,/를 모두 사용하면서 연산을 진행하면 굉장히 많은 경우의 수가 나올 것 같지만
생각해보면 '-'는 사용할 일이 없습니다. '-' 연산을 사용하면 무조건 0이 되는데
결과값인 t이 1 이상이기 때문에 어떤 입력에도 0을 만들 일이 없습니다.
'/'의 사용시 무조건 1을 만들기 때문에 최초 1회에만 사용하는 것이 의미가 있습니다.

결국 시작 숫자 s에서 *,+를 이용해 t를 만드는 경우와, 처음에 '/' 연산을 사용해
1을 만든 뒤 *,+를 이용해 t를 만드는 경우 둘 중 최적의 경우를 찾으면 됩니다.

수의 범위가 10^9이므로 많은 수가 등장할 것 같지만 +,* 연산을 이용할 경우 수가 큰 폭으로 증가하므로
10^9에 도달할 때까지 10^9만큼 많은 수가 등장하지는 않을 것입니다.
이를 이용해 set으로 visit한 숫자에 체크를 해주는 BFS를 사용할 수 있습니다.

s부터 시작해 t를 만든 경우, '/' 연산을 사용해 1부터 시작해 t를 만든 두 경우를 비교해서
최적의 답을 구해주면 됩니다.

#include <cstdio>
#include <string>
#include <set>
#include <iostream>
#include <queue>
using namespace std;
using ll = long long;
ll s,t;
string sol(ll sv,string sstr){
    queue<pair<ll,string>> q;
    q.push({sv,sstr});   
    set<ll> visit;
    visit.insert(sv);
    while(!q.empty()){
        auto [v,str] = q.front();
        q.pop();
        if(v==t) return str;

        if(v*v<=t && visit.find(v*v)==visit.end()) {
            visit.insert(v*v);
            q.push({v*v,str+"*"});
        }
        if(v+v<=t && visit.find(v+v)==visit.end()) {
            visit.insert(v+v);
            q.push({v+v,str+"+"});
        }

    }     
    return "0";
}
int main(){
    cin >> s >> t;
    if(s==t) {
        cout << 0;
        return 0;
    }
    string ans1 = sol(s,"");
    string ans2 = sol(1,"/");
    if(ans1=="0" && ans2=="0") cout << -1;
    else if(ans1=="0") cout << ans2;
    else if(ans2=="0") cout << ans1;
    else {
        if(ans1.size()<ans2.size()) cout << ans1;
        else if(ans1.size()>ans2.size()) cout << ans2;
        else{
            if(ans1<ans2) cout << ans1;
            else cout << ans2;    
        }   
    }
}

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

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

[난이도] Gold5
[유형] DP

[풀이]
전형적인 배낭문제입니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,T,dp[10001];
pair<int,int> p[100];
int main(){
    scanf("%d%d",&N,&T);
    for(int i=0;i<N;i++) scanf("%d%d",&p[i].first,&p[i].second);
    for(int i=0;i<N;i++){
        for(int j=T;j>=0;j--){
            if(j-p[i].first>=0) dp[j] = max(dp[j],dp[j-p[i].first]+p[i].second);
        }
    }
    int ans=0;
    for(int i=1;i<=T;i++) ans=max(ans,dp[i]);
    printf("%d",ans);
}

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

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

[난이도] Gold5
[유형] DP

[풀이]
top-down dp를 이용해 해결할 수 있습니다.
dp[n] : s[n..N-1] 을 만들 수 있는 경우의 수.

1자리수를 선택하는 경우와 2자리수를 선택하는 경우를 나누어서 dp[n] 에 더해주면 됩니다.
두자리수 s[n..n+1]이 35보다 적은 경우 dp[n+2]를 더해줄 수 있습니다.
s[n]이 '0'인 경우는 예외처리를 해주어야 합니다.

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
using ll = long long;
int N;
ll dp[41];
string s;
ll sol(int n){
    if(n==N) return 1;
    ll& ret = dp[n];
    if(ret!=-1) return ret;
    ret=0;
    if(s[n]=='0') return 0;
    if(n<N-1) {
        string a = s.substr(n,2);
        if(stoi(a)<35){
            ret+=sol(n+2);
            if(a[1]=='0') return ret;
        }
    }
    ret+=sol(n+1);
    return ret;
}
int main(){
    cin >> s;
    N = s.size();
    memset(dp,-1,sizeof(dp));
    printf("%lld",sol(0));
}

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

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

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

[풀이]
정육면체는 탁자위에서 보이는 정육면체의 면은 크게 3가지로 나눌 수 있습니다.
3면이 인접한 부분, 두 면이 인접한 부분, 한 면만 보이는 부분

1x1x1 짜리 주사위의 모양을 미리 알고 있으므로 위 3가지 모양의 최솟값을 미리 구해놓고
각각이 NxNxN 정육면체에 몇번 들어가는지를 구하면 됩니다.

3면이 인접한 부분, 두 면이 인접한 부분, 한 면만 보이는 부분의 최솟값을 각각
p,q,r이라고 하면

p는 정육면체의 맨 위의 꼭짓점 이므로 4*p ,
q는 탁자에 붙어있는 아래의 꼭짓점 4개와 탁자에 붙어있는 모서리를 제외한 8개의 모서리에
각각 N-2개만큼 존재하므로 4*q+8*(N-2)*q ,
r은 그 이외의 모든 면이므로 4*(N-2)*r+5*(N-2)*(N-2)*r

#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;
ll N,a[6];
int main(){
    ll p=200,q=200,r=200;
    scanf("%lld",&N);
    for(int i=0;i<6;i++) {
        scanf("%lld",&a[i]);
        r=min(r,a[i]);
    }
    if(N==1) {
        int sum=0,m=0;
        for(int i=0;i<6;i++){
            sum+=a[i];
            m=max(m,(int)a[i]);
        }
        printf("%d",sum-m);
        return 0;
    }
    p=min(p,a[0]+a[1]+a[2]);
    p=min(p,a[0]+a[3]+a[4]);
    p=min(p,a[0]+a[1]+a[3]);
    p=min(p,a[0]+a[2]+a[4]);
    p=min(p,a[5]+a[3]+a[4]);
    p=min(p,a[5]+a[1]+a[3]);
    p=min(p,a[5]+a[1]+a[2]);
    p=min(p,a[5]+a[2]+a[4]);
    for(int i=0;i<6;i++){
        for(int j=0;j<6;j++){
            if(i!=j && i+j!=5) q=min(q,a[i]+a[j]);
        }
    }
    ll ans = 4*p+4*q+8*(N-2)*q+4*(N-2)*r+5*(N-2)*(N-2)*r;
    printf("%lld",ans);
}

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

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

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

[풀이]
총 6개의 0~5번 팀이 있다고 했을 때, 게임은 아래와 같이 총 15개가 나옵니다.
{{0,1},{0,2},{0,3},{0,4},{0,5},
 {1,2},{1,3},{1,4},{1,5},
 {2,3},{2,4},{2,5},
 {3,4},{3,5},
 {4,5}}

(p,q)가 게임하는 게임에 대해 p승,q패 / p패, q승 / p무, q무 총 3가지 경우가 나옵니다.
15개의 각 게임에 대해 백트래킹을 이용하여 3가지 경우를 모두 해보는 방식으로 문제를 해결할 수 있습니다.
3^15 = 14348907 이므로 시간내에 해결이 가능합니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int a[6][3];
pair<int,int> g[] = {{0,1},{0,2},{0,3},{0,4},{0,5},
                     {1,2},{1,3},{1,4},{1,5},
                     {2,3},{2,4},{2,5},
                     {3,4},{3,5},
                     {4,5}};
bool sol(int n){
    if(n==15){
        for(int i=0;i<6;i++)
            for(int j=0;j<3;j++) if(a[i][j]) return false;
        return true;  
    }
    auto [p,q] = g[n];
    if(a[p][1] && a[q][1]) {
        a[p][1]--,a[q][1]--;
        if(sol(n+1)) return true;
        a[p][1]++,a[q][1]++;
    }
    if(a[p][0] && a[q][2]) {
        a[p][0]--,a[q][2]--;
        if(sol(n+1)) return true;
        a[p][0]++,a[q][2]++;
    }
    if(a[p][2] && a[q][0]) {
        a[p][2]--,a[q][0]--;
        if(sol(n+1)) return true;
        a[p][2]++,a[q][0]++;
    }
    return false;
}
int main(){
    for(int i=0;i<4;i++){
        for(int j=0;j<6;j++)
            for(int k=0;k<3;k++) scanf("%d",&a[j][k]);
        printf("%d ",sol(0));
    }
}

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