프로그래밍

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

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

[풀이]
두번째 수를 1~N까지 모든 수로 바꿔보면서 수열을 구해주면 됩니다.

#include <cstdio>
#include <vector>
using namespace std;
int N;
vector<int> ans;
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        vector<int> tmp;
        tmp.push_back(N);
        tmp.push_back(i);
        for(int j=1;;j++){
            if(tmp[j-1]-tmp[j]<0) break;
            tmp.push_back(tmp[j-1]-tmp[j]);
        }
        if(tmp.size()>ans.size()) ans=tmp;
    }
    printf("%d\n",ans.size());
    for(auto v : ans) printf("%d ",v);
}

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

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

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

[풀이]
주어진 4가지 숫자를 이용해 만들 수 있는 수를 모두 만들면서 가장 작은 수를 찾아 시계수를 만들어 줍니다.
그 뒤에 1111 부터 모든 수를 문제에서 주어진 시계수가 나올때까지 체크해주면서 0을 포함하거나, 시계수가 아닌 수를 제외해서 해주면 됩니다.

#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int a[4];
string check(string o){
    vector<string> v;
    for(int i=0;i<4;i++){
        string s;
        for(int j=0;j<4;j++){
            s+=o[(i+j)%4];
        }
        v.push_back(s);
    }
    sort(v.begin(),v.end());
    return v[0];
}
int main(){
    for(int i=0;i<4;i++) scanf("%d",&a[i]);
    vector<string> v;
    for(int i=0;i<4;i++){
        string s;
        for(int j=0;j<4;j++){
            s+=to_string(a[(i+j)%4]);
        }
        v.push_back(s);
    }
    sort(v.begin(),v.end());
    int ans=1;
    for(int i=1111;;i++){
        string s = to_string(i);
        if(s.find("0") != string::npos) continue;
        if(check(s)!=s) continue;
        if(s==v[0]) break;
        ans++;
    }
    printf("%d",ans);
}

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

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

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

[풀이]
100x100 board 배열을 선언한 뒤, 각 4개의 사각형을 체크하면서
차지하는 영역에 체크를 해준 뒤 체크된 영역을 더해주면 됩니다.

#include <cstdio>
int a,b,c,d,board[101][101],ans;
int main(){
    for(int i=0;i<4;i++){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        for(int i=a;i<c;i++)
            for(int j=b;j<d;j++) board[i][j]=1;
    }
    for(int i=0;i<=100;i++)
        for(int j=1;j<=100;j++) ans+=board[i][j];
    printf("%d",ans);
}

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

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

[난이도] Gold2
[유형] 큰 수 연산

[풀이]
나중에..

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int T,m;
string a,b;
vector<int> sol2(string s){
    vector<int> ret(m+1);
    int cur=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='(') cur++;
        else {
            cur--;
            if(s[i-1]=='('){
                ret[cur]++;
            }
        }
    }
    for(int i=0;i<ret.size()-1;i++){
        ret[i+1]+=ret[i]/2;
        ret[i]%=2;
    }
    return ret;
}
string sol(){
    vector<int> pa = sol2(a);
    vector<int> pb = sol2(b);
    for(int i=pa.size()-1;i>=0;i--){
        if(pa[i] < pb[i]) return "<";
        if(pa[i] > pb[i]) return ">"; 
    }
    return "=";
}
int main(){
    cin >> T;
    while(T--){
        cin >> a >> b;
        m=max(a.size(),b.size());
        m/=2;
        cout << sol() << '\n';
    }
}

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

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

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

[풀이]
문제의 조건대로 구현

#include <cstdio>
int N,C,cy,cx;
int main(){
    scanf("%d%d",&N,&C);
    cy=N,cx=N;
    while(C--){
        int y,x;
        scanf("%d%d",&y,&x);
        if(y>cy||x>cx) continue;
        int ny=y,nx=cx,w=y*cx;
        if(w<cy*x){
            ny=cy,nx=x;
        }
        cy=ny,cx=nx;
    }
    printf("%d",cy*cx);
}

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

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

[난이도] Gold1
[유형] Greedy

[풀이]
나중에..

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int N,K;
ll v[4];
priority_queue<int> pq[4];
struct P{
    int idx,l;
};
bool cmp(P& a,P& b){
    return (a.l+v[a.idx])*v[b.idx] > (b.l+v[b.idx])*v[a.idx];
}
int main(){
    scanf("%d%d",&N,&K);
    for(int i=0;i<4;i++) scanf("%d",&v[i]);
    while(N--){
        char c;
        int l;
        scanf(" %c %d",&c,&l);
        pq[c-'A'].push(l);
    }
    while(K--){
        vector<P> t;
        for(int i=0;i<4;i++){
            if(pq[i].empty()) continue;
            t.push_back({i,pq[i].top()});
        }
        sort(t.begin(),t.end(),cmp);
        auto [idx,l] = t[0];
        pq[idx].pop();
        v[idx]+=l;
        printf("%c %d\n",idx+'A',l);
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold1/초직사각형.cpp

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

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

[풀이]
N,M,k,D가 모두 주어지고 A=k*B 이기 때문에 식을 잘 세워보면
미지수는 B밖에 남지 않는 다는 것을 알 수 있습니다.
식을 잘 정리한 뒤 반복문을 이용해 B가 조건을 만족하지 않을 때까지 증가시켜가며 B의 최적값을 찾아주면 됩니다.

#include <algorithm>
using namespace std;
using ll = long long;
int T;
ll N,M,k,D;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld%lld%lld",&N,&M,&k,&D);
        ll B=0;
        while(N*M*B*(k*(M-1)+M*(N-1))<=2*D) B++;
        if(B<=1) {
            puts("-1");
            continue;
        }
        ll a=N*M*(B-1)*(k*(M-1)+M*(N-1));
        printf("%lld\n",a/2);
    }
}

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

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

[난이도] Silver1
[유형] 누적 합

[풀이]
N개의 장소가 a[1]~a[N] 일 때, 아래 3가지 경우에 대해 각각 계산해보면서 답을 갱신해주면 됩니다.
계산의 시간을 줄이려면 1~N의 누적합을 미리 구해두어야 합니다.

case1) 벌통이 index 1 에 있는 경우
벌 한마리는 index N에 있어야 하고,
나머지 한마리는 어디에 있는 것이 최적인지 알 수 없으므로
2~N-1에 나머지 한마리가 있는 경우 모두를 계산해 줍니다.
누적합을 이용하면 각 경우를 O(1)에 계산이 가능하므로 O(N)에 모든 경우를 계산 가능합니다.

case2) 벌통이 index N 에 있는 경우
벌 한마리는 index 1에 있어야 하고, 나머지 계산은 case1과 동일합니다.

case3) 벌통이 1과 N 사이에 있는 경우
벌은 1과 N에 있는 것이 최적입니다. 벌통을 2~N-1으로 옮겨보면서 계산해줍니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,sum[100001],a[100001],ans;
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) {
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=2;i<N;i++) {
        ans=max(ans,2*sum[N]-a[1]-a[i]-sum[i]);
        ans=max(ans,sum[N-1]-a[i]+sum[i-1]);
        ans=max(ans,sum[i]-a[1]+sum[N-1]-sum[i-1]);
    }
    printf("%d",ans);
}

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