프로그래밍

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

[난이도] Gold5
[유형] Greedy

[풀이]
모든 강의의 시작 시간과 종료 시간을 동일한 vector<pair<int,int>>에 저장합니다.
시작 시간의 경우 +1을, 종료 시간은 -1을 묶어서 pair의 second에 저장해줍니다.
그 뒤 시간으로 정렬을 해준 뒤 second를 cur 변수에 더해주면서 이것의 최댓값을 갱신해주면 이것이 정답이 됩니다.
그 이유는 어떤 강의가 시작될때 1을 더해주고 끝날 때 1을 빼주게 되므로
동시에 진행중인 강의의 수가 cur에 저장되게 되기 때문입니다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct P{
    int s,e;
};
int N,ans;
vector<pair<int,int>> a;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        int t,s,e;
        scanf("%d%d%d",&t,&s,&e);
        a.push_back({s,1});
        a.push_back({e,-1});
    }
    sort(a.begin(),a.end());
    int cur=0;
    for(auto [v,m] : a){
        cur+=m;
        ans=max(cur,ans);
    }
    printf("%d",ans);
}

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

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

[난이도] Gold5
[유형] DP

[풀이]
DP[c] : 고객을 적어도 c명 늘이기 위해 투자해야하는 최솟값
배낭문제 응용입니다.
0~N-1까지 반복문을 돌려주면서 i번 도시까지 홍보할때의 최솟값을 DP 배열에 순차적으로 저장해주면 됩니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int C,N,p[20],cost[20],dp[1001],inf=9e8;
int main(){
    scanf("%d%d",&C,&N);
    for(int i=0;i<N;i++) scanf("%d%d",&cost[i],&p[i]);
    for(int i=1;i<=C;i++) dp[i]=inf;
    for(int i=0;i<N;i++){
        for(int j=1;j<=C;j++){
            for(int k=1;;k++){
                int v=0;
                if(j-p[i]*k>=0) v=dp[j-p[i]*k];
                if(dp[j] > v+cost[i]*k) dp[j] = v+cost[i]*k;
                else break;
            }
        }
    }
    printf("%d",dp[C]);
}

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

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

[난이도] Gold5
[유형] BFS

[풀이]
간단한 Greedy + BFS 문제입니다.

그냥 BFS를 돌리면 N 범위가 10000000 이고, tc개수가 100이므로 시간초과가 발생합니다.
잘 생각해보면 0에서 N을 만들 때, ADDH 연산 (t+60)을 가장 많이 사는것이 연산 횟수를
줄이는데 유리합니다.

N/60 만큼 ADDH 연산을 사용한 뒤, N%60 을 ADDH 외의 연산으로 만들때의 최적값과,

N/60+1만큼 ADDH 연산을 사용한 뒤, 60-N%60을 ADDH 외의 연산으로 만들때의 최적값을

BFS를 이용해 각각 구해준 뒤, 연산 횟수가 더 적은 케이스를 답으로 출력해주면 됩니다.

예를 들어, N이 134라면 60*2 + 14 와 60*3 - 46 을 비교하는 것과 같습니다.

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int tc,N,a[]={10,-10,1,-1},visit[80];
vector<int> bfs(int k,int m){
    memset(visit,0,sizeof(visit));
    queue<vector<int>> q;
    visit[0]=1;
    q.push({0,0,0,0,0});
    while(1){
        int sz = q.size(); 
        while(sz--){
            auto cur = q.front(); q.pop();
            if(cur[4]==m) {
                vector<int> r = {k};
                for(int i=0;i<4;i++) r.push_back(cur[i]);
                return r;
            }
            for(int i=0;i<4;i++){
                int nxt = cur[4]+a[i];
                if(nxt<0 || nxt>70 || visit[nxt]) continue;
                visit[nxt]=1;
                auto nv = cur;
                nv[i]++;
                nv[4]=nxt;
                q.push(nv);
            }
        }
    }
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);

        int k = N/60;
        int mod = N%60;

        auto ret1 = bfs(k,mod);
        int cnt1=0;
        for(int i=0;i<5;i++) cnt1+=ret1[i];

        auto ret2 = bfs(k+1,60-mod);
        int cnt2=0;
        for(int i=0;i<5;i++) cnt2+=ret2[i];
        swap(ret2[1],ret2[2]);
        swap(ret2[3],ret2[4]);

        if(cnt1>cnt2){
            for(int i=0;i<5;i++) printf("%d ",ret2[i]);
        }else{
            for(int i=0;i<5;i++) printf("%d ",ret1[i]);
        }
        puts("");
    }
}

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

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

[난이도] Gold5
[유형] DP

[풀이]
DP[i] : s가 길이 n인 암호 문자열일 때, s[i..n-1] 로 만들 수 있는 해석의 총 개수.

#include <string>
#include <iostream>
#include <cstring>
using namespace std;
int dp[5001];
string s;
int sol(int n){
    if(n>=s.size()) return 1;
    int& ret = dp[n];
    if(ret!=-1) return ret;
    if(s[n]=='0') return 0;
    ret=sol(n+1);
    if(n+1<s.size()){
        int k = (s[n]-'0')*10+(s[n+1]-'0');
        if(k<27) ret=(ret+sol(n+2))%1000000;
    }
    return ret;
}
int main(){
    cin >> s;
    memset(dp,-1,sizeof(dp));
    cout << sol(0);
}

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

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

[난이도] Gold1
[유형] DP

[풀이]
dp[l][r] : s[l~r]가 팰린드롬이면 1, 아니면 0
dp2[i] : 문자열의 길이가 N일때, 부분문자 s[i~(N-1)] 에서 분할 개수의 최솟값

dp[2501][2501]을 dp를 이용해 구한 뒤,
이를 이용해 dp2[2501]도 dp로 구해주면 됩니다.

#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
string s;
int N,dp[2501][2501],dp2[2501];
int sol(int l,int r){
    if(l>=r) return 1;
    int& ret = dp[l][r];
    if(ret!=-1) return ret;
    if(s[l]==s[r]) ret=sol(l+1,r-1);
    else ret=0;
    return ret;
}
int sol2(int n){
    if(n==N) return 0;
    int& ret = dp2[n];
    if(ret!=-1) return ret;
    ret=9e8;
    for(int i=n;i<N;i++)
        if(dp[n][i]) ret=min(ret,1+sol2(i+1));
    return ret;
}
int main(){
    cin >> s;
    N=s.size();
    memset(dp,-1,sizeof(dp));
    memset(dp2,-1,sizeof(dp2));
    for(int i=0;i<s.size()-1;i++)
        for(int j=i+1;j<s.size();j++) sol(i,j);
    cout << sol2(0);
}

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

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

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

[풀이]
N이 15밖에 되지 않으므로 모든 경우의 수를 재귀함수를 이용해 다 해보면 됩니다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct P{
    int p,f,s,v,c;
};
int N,mp,mf,ms,mv,ansv=9e8;
P a[15];
vector<int> vec,ans;
void sol(int n,int p,int f,int s,int v,int c){
    if(n==N){
        if(p>=mp&&f>=mf&&s>=ms&&v>=mv){
            if(ansv>c){
                ans=vec;
                ansv=c;
            }else if(ansv==c && ans>vec){
                ans=vec;
                ansv=c;                
            }
        }
        return;
    }
    sol(n+1,p,f,s,v,c);
    vec.push_back(n);
    sol(n+1,p+a[n].p,f+a[n].f,s+a[n].s,v+a[n].v,c+a[n].c);
    vec.pop_back();
}
int main(){
    scanf("%d%d%d%d%d",&N,&mp,&mf,&ms,&mv);
    for(int i=0;i<N;i++){
        scanf("%d%d%d%d%d",&a[i].p,&a[i].f,&a[i].s,&a[i].v,&a[i].c);
    }
    sol(0,0,0,0,0,0);
    if(ansv==9e8){
        puts("-1");
        return 0;
    }
    printf("%d\n",ansv);
    for(auto k : ans) printf("%d ",k+1);
}

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

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

[난이도] Platinum5
[유형] DP

[풀이]
O(nlogn) LIS 문제입니다.

#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int N,mp[500001],pos[100001];
pair<int,int> a[100001];
set<int> ans;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        scanf("%d%d",&a[i].first,&a[i].second);
        ans.insert(a[i].first);
    }
    sort(a,a+N);
    for(int i=0;i<N;i++) mp[a[i].second]=i;

    vector<int> v;
    for(int i=0;i<N;i++){
        int idx = lower_bound(v.begin(),v.end(),a[i].second)-v.begin();
        if(v.size()==idx) v.push_back(a[i].second);
        else v[idx]=a[i].second;
        pos[i]=idx;
    }
    int k=v.size()-1;
    for(int i=N-1;i>=0;i--){
        if(pos[i]==k){
            ans.erase(a[i].first);
            if(--k<0) break;
        }
    }
    printf("%d\n",ans.size());
    for(auto k : ans) printf("%d\n",k);
}

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

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

[유형] DP

[풀이]
bitmask를 이용한 3차원 dp를 이용해 해결이 가능합니다.

dp[n][m][bit] : 맨 앞자리수가 m이면서, 길이가 n이고, bit에 mask된 숫자들을 사용한 숫자들의 개수

#include <cstdio>
#include <cstring>
using namespace std;
int N,dp[101][10][1<<10],mod=1e9;
int sol(int n,int m,int bit){
    if(n==N) return ((1<<m)|bit)==((1<<10)-1);

    int& ret = dp[n][m][bit];
    if(ret!=-1) return ret;
    ret=0;
    bit |= (1<<m);
    if(m-1>=0) ret=(ret+sol(n+1,m-1,bit))%mod;
    if(m+1<10) ret=(ret+sol(n+1,m+1,bit))%mod;
    return ret;
}
int main(){
    scanf("%d",&N);
    memset(dp,-1,sizeof(dp));
    int ans=0;
    for(int i=1;i<10;i++){
        ans+=sol(1,i,0);
        ans%=mod;
    }
    printf("%d",ans);
}

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