프로그래밍

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

[난이도] Gold4
[유형] Greedy

[풀이]
3이 최대만 많이 되도록
3^k , 3^k*2, 3^k*4 의 형태로 만들어 주면 가장 큰 수를 만들 수 있습니다.
즉 3으로 나눴을 때 나머지가 1이면  3^k*4의 형태로, 나머지가 2이면 3^k*2로 만들어 주면 됩니다.

예제5번의 답이 3^k * 4의 형태라 여기서 힌트를 얻었지만 수학적으로 왜 그렇게 되는지는 분석이 필요할 것 같습니다.

#include <cstdio>
using namespace std;
int N,mod=10007;
int main(){
    scanf("%d",&N);
    if(N==0){
        puts("0");
        return 0;
    }

    int k = N/3;
    int m = N%3;
    int ret=1;
    if(m==1) {
        if(k>0) {
            k--;
            ret=4;
        }
    }else if(m==2){
        ret=2;
    }

    for(int i=0;i<k;i++) ret=(ret*3)%mod;
    printf("%d",ret); 
}

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

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

[난이도] Gold4
[유형] DP

[풀이]
map을 이용해 메모제이션을 해주면 long long 형의 큰 수도 저장할 수 있습니다.
i/P, i/Q와 같이 P,Q로 나눈 후의 수들만 필요하기 때문에 너무 많은 수가 저장되는 것을 저장할 필요가 없습니다.

#include <cstdio>
#include <map>
using namespace std;
using ll = long long;
ll N,P,Q,X,Y;
map<ll,ll> dp;
ll sol(ll n){
    if(n<=0) return 1;
    if(dp.find(n)!=dp.end()) return dp[n];
    return dp[n] = sol(n/P-X)+sol(n/Q-Y);
}
int main(){
    scanf("%lld%lld%lld%lld%lld",&N,&P,&Q,&X,&Y);
    printf("%lld",sol(N));
}

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

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

[난이도] Gold4
[유형] DP

[풀이]
구슬의 종류가 최대 5개밖에 되지 않고, 각각 10개 이하이기 때문에 7차원 DP로 해결할 수 있습니다.
long long dp[7][7][11][11][11][11][11] 배열을 이용하였습니다.
dp[prev][cur][a][b][c][d][f]에서 cur은 이전에 선택한 구슬의 색, prev는 cur 이전에 선택한 구슬의 색이며
a,b,c,d,f는 각각 구슬의 남은 개수입니다.

prev와 cur이 아닌 구슬을 선택하는 경우의 수를 더해주면 됩니다.
모든 구슬을 사용했을 때가 가능한 경우의 수가 되므로 1을 return 해서 정답에 포함될 수 있게 해줍니다.

#include <cstdio>
#include <cstring>
using namespace std;
using ll = long long;
int N,a[6];
ll dp[7][7][11][11][11][11][11];
ll sol(int prev,int cur,int a,int b,int c,int d,int f){
    if(a==0&&b==0&&c==0&&d==0&&f==0) return 1;
    ll& ret=dp[prev][cur][a][b][c][d][f];
    if(ret!=-1) return ret;
    ret=0;
    if(a>0 && prev!=0 && cur!=0) ret+=sol(cur,0,a-1,b,c,d,f);
    if(b>0 && prev!=1 && cur!=1) ret+=sol(cur,1,a,b-1,c,d,f);
    if(c>0 && prev!=2 && cur!=2) ret+=sol(cur,2,a,b,c-1,d,f);
    if(d>0 && prev!=3 && cur!=3) ret+=sol(cur,3,a,b,c,d-1,f);
    if(f>0 && prev!=4 && cur!=4) ret+=sol(cur,4,a,b,c,d,f-1);
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    memset(dp,-1,sizeof(dp));
    printf("%lld",sol(6,5,a[0],a[1],a[2],a[3],a[4]));
}

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

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

[난이도] Gold4
[유형] 이분탐색

[풀이]
규칙성을 찾아서 수학적 수식으로 푸는것이 정해인 것 같은데
무식하게 이분탐색으로 풀었습니다.

A<= x <=B 인 x에 대해
x가 2^k * p (k>=1) 꼴로 나타내지는 것들에 대해서는 2^k 만큼 더해주면 됩니다.

결국 B를 넘지 않는 모든 2^k에 대해
A<= 2^k * p <=B 를 만족하도록 하는 p의 범위를 구해주면 됩니다.

이를 이분탐색으로 구할 수 있습니다.
A<= 2^k * left <= 2^k* right <= B
A보다 크거나 같게 만드는 left, B보다 작거나 같게 만드는 right를 이분탐색으로 각각 구하면
right-left+1 만큼이 A<= 2^k * p <=B 를 만족하는 p의 개수가 됩니다.
결국 정답 ans에 2^k * (right-left+1)를 더해주면 됩니다.

주의할 것이 k의 최댓값부터 반대로 검사를 해주면서 acnt (정답에 포함된 A<= x <= B 인 x의 개수) 를 누적해주어야 합니다. 2^k 에서 답에 누적된 x들은 2^(k-1) 에 반드시 포함되므로 이것을 빼줘야 하기 때문입니다.
그래서 right-left+1 대신 right-left+1-acnt를 사용하였습니다.

#include <cstdio>
#include <vector>
using namespace std;
using ll = long long;
ll A,B;
ll bsearch(ll v,ll lo,ll hi,ll c,bool left){
    while(lo+1<hi){
        ll mid = (lo+hi)/2;
        if(v*mid>c) hi=mid;
        else if(v*mid<=c) lo=mid;
    }
    if(left){
        if(lo*v<c) lo++;
    }else{
        if(lo*v>c) lo--;
    }
    return lo;
}
int main(){
    scanf("%lld%lld",&A,&B);

    vector<ll> vec;
    for(ll i=2;;i*=2){
       if(i>B) break;
       vec.push_back(i);
    }
    ll ans=0,acnt=0;
    for(int i=vec.size()-1;i>=0;i--){
        ll v = vec[i];
        ll lo=1,hi=(1e15+2)/v;
        ll left = bsearch(v,lo,hi,A,1);
        ll right = bsearch(v,lo,hi,B,0);
        if(left<=right && v*left>=A && v*right<=B) {
            ll cur = right-left+1-acnt;
            acnt+=cur;
            ans+=cur*v;
        }
    }
    printf("%lld",ans+(B-A+1-acnt));
}

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

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

[난이도] Gold4
[유형] Greedy

[풀이]
방 번호를 가장 크게 만드려면, 방 번호 숫자의 길이를 가장 길게 만들어야 하며,
그 뒤 가장 큰 자리수의 수들을 큰 수, 즉 N-1과 가까운 수로 만들수록 유리합니다.

이런 수를 만들기 위해 vector<pair<가격,숫자>> p 를 만들고 입력받은 값을 저장해준 뒤
정렬해주어 가격이 싼 것이 앞으로 오도록 합니다.
p[0]가 가장 싼 숫자가 되며, 주어진 돈 M을 이용해  이 숫자를 최대한 많이 사면
숫자를 가장 많이 살 수 있기 때문에 방 번호를 가장 길게 만들 수 있습니다.
이렇게 p[0].second 숫자로만 이루어진 string ret을 만들어 놓고

남은 돈을 이용해 ret[0],ret[1],ret[2]..... 순으로 가능하면 N-1에 가까운 숫자로 바꿔주면
가장 큰 방번호를 만들 수 있습니다.

주의해야 할 것이 p[0].second가 0이라면 전체 숫자가 0이 되지 않도록 가장 앞 숫자를 p[1].second가 되도록
해주어야 합니다.

#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int N,M,P[10];
vector<pair<int,int>> p;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        scanf("%d",&P[i]);
        p.push_back({P[i],i});
    }
    scanf("%d",&M);
    sort(p.begin(),p.end());
    string ret;
    if(N==1){
        puts("0");
        return 0;
    }
    if(p[0].second!=0){
        int cnt = M/p[0].first;
        for(int i=0;i<cnt;i++) ret+=to_string(p[0].second);
        M-=cnt*p[0].first;
    }else{
        int m = M - p[1].first;
        if(m<0) {
            puts("0");
            return 0;
        }
        ret+=to_string(p[1].second);
        int cnt = m/p[0].first;
        for(int i=0;i<cnt;i++) ret+=to_string(p[0].second);
        M=m-cnt*p[0].first;
    }
    for(int i=0;i<ret.size();i++){
        bool ok=0;
        int cur = P[ret[i]-'0'];
        for(int j=N-1;j>=0;j--){
            if(M-(P[j]-cur)>=0){
                M-=P[j]-cur;
                ok=1;
                ret[i]=j+'0';
            }
            if(ok) break;
        }
        if(!ok) break;
    }
    printf("%s",ret.c_str());
}

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

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

[난이도] Gold3
[유형] DP

[풀이]
단어의 개수와 길이가 50으로 작기 때문에 다이나믹 프로그래밍으로 해결이 가능합니다.

dp 배열은 다음과 같이 정의가 가능하며
dp[n] : 문장 string을 s라고 했을 때, s[n~s.size()-1] 인 substring을 해석하기 위해 필요한 최소 연산

점화식은 다음과 같습니다.
dp[n] = dp[i+1] + [s[n~i]인 substring을 해석하는데 필요한 cost] ( n<=i<s.size()-1)

모든 N개의 단어를 substring s[n~i]으로 변환하는데 드는 cost 중 최솟값을 위의 cost로 사용하면 됩니다.
아래 코드에서는 일단 비교하는 두 string을 정렬하여 비교함으로써 정확히 같은
문자들을 가지고 있는지 확인하였고, 원본 string을 다시 비교하면서 위치가 다른 문자들의 개수를 세서
전체 문자 길이에서 빼주었습니다.

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
string s,word[50];
int dp[51],N,inf=9e8;
int cost(string a,string b){
    if(a.size()!=b.size()) return inf;
    string ta = a;
    string tb = b;
    sort(ta.begin(),ta.end());
    sort(tb.begin(),tb.end());
    if(ta!=tb) return inf;

    int ret = a.size();
    for(int i=0;i<a.size();i++){
        if(a[i]==b[i]) ret--;
    }
    return ret;
}
int minCost(string k){
    int ret = inf;
    for(int i=0;i<N;i++) ret = min(ret,cost(k,word[i]));
    return ret;
}
int sol(int n){
    if(n==s.size()) return 0;
    int& ret = dp[n];
    if(ret!=-1) return ret;
    ret = inf;
    for(int i=n;i<s.size();i++){
        string k = s.substr(n,i-n+1);
        int c = minCost(k);
        if(c==inf) continue;
        ret = min(ret,c+sol(i+1));
    }
    return ret;
}
int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(0);
    cin >> s >> N;
    for(int i=0;i<N;i++) cin >> word[i];
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0)==inf ? -1 : sol(0));
}

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

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

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

[풀이]
map[100][100] 배열에 색종이가 있는 영역은 1로 채워 준 뒤

width : 1~100, height : 1~100 총 100 x 100개의 넓이에 대해서
(0,0) ~ (99,99) 을 왼쪽 끝 점으로 해서 만들 수 있는지를 브루트포스로 확인해주면 됩니다.

얼핏보면 100x100 x 100x100 x 100x100 = O(10^12) 으로 시간초과가 날 것 같지만
(0,0) ~ (99,99) 점에서 시작하는 직사각형을 만드는 과정이 생각보다 많은 시간이 들지 않습니다.
(코드에서는 bool check(int h,int w,int y,int x) 함수)

왜냐하면 넓이가 커지면 검사해야 하는 점이 줄어들고,
(예를들어 100x100인 경우 (0,0)만 검사하면 됨)

넓이가 작아지면 검사 시간이 적게 걸리기 때문입니다.
(예를들어 1x1인 경우 (0,0)~(99,99) 점을 검사해야 하지만 각각 1의 연산 밖에 들지 않음)

#include <cstdio>
#include <algorithm>
using namespace std;
int N,map[100][100];
bool check(int h,int w,int y,int x){
    for(int i=y;i<y+h;i++)
        for(int j=x;j<x+w;j++)
            if(!map[i][j]) return false;
    return true;
}
bool check(int h,int w){
    for(int i=0;i<=100-h;i++)
        for(int j=0;j<=100-w;j++)
            if(check(h,w,i,j)) return true;
    return false;
}
int main(){
    scanf("%d",&N);
    while(N--){
        int x,y;
        scanf("%d%d",&x,&y);
        for(int i=y;i<y+10;i++)
            for(int j=x;j<x+10;j++) map[i][j]=1;
    }
    int ans=0;
    for(int i=1;i<=100;i++)
        for(int j=1;j<=100;j++)
            if(check(i,j)) ans=max(ans,i*j);

    printf("%d",ans);
}

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

https://codeforces.com/contest/1598/problem/B

[난이도] Div.2
[유형] 브루트포스

[풀이]
두 클래스는 월~금 중 두가지가 되어야 하므로 5C2 = 10 개의 케이스에 대해
체크를 해줍니다. 두 요일 u,v에 대해
u만 참여 가능한 학생을 f1에,
v만 참여 가능한 학생을 f2에,
둘다 참여 가능한 학생을 f12에 저장합니다.
이를 이용해 u,v에 정확히 같은 수의 학생이 들어갈 수 있는지를 확인할 수 있습니다.
먼저 모든 학생이 참가해야 하므로 f1+f2+f12 == n 이 되어야 합니다.
현재 f1, f2가 정확히 같은 수가 아니라면 f12에서 부족한 쪽을 채워 줍니다.
그 뒤에 f12가 짝수라면 정확히 같은 수의 학생으로 나눌 수 있기 때문에 YES를 출력해주면 됩니다.

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
int t,n,a[1000][5];

bool check(int u,int v){
    int f1=0,f2=0,f12=0;

    for(int i=0;i<n;i++){
        if(a[i][u] && a[i][v]) f12++;
        else if(a[i][u]) f1++;
        else if(a[i][v]) f2++;
    }
    if(f1+f2+f12!=n) return false;

    if(f1>f2) swap(f1,f2);
    f12-=f2-f1;

    if(f12<0) return false;

    if(f12%2) return false; 

    return true;
}
bool sol(){
    for(int i=0;i<4;i++){
        for(int j=i+1;j<5;j++){
            if(check(i,j)) return true;
        }
    }
    return false;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            for(int j=0;j<5;j++) scanf("%d",&a[i][j]);
        }
        puts(sol()?"YES":"NO");

    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/RoundEDU115-Div.2/B.cpp