프로그래밍

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

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

[풀이]
double형으로 입력을 받고 문제의 조건대로 평균들을 구해주면 됩니다.
반올림 처리가 중요한데.
a라는 숫자를 소숫점 3번째에서 반볼림을 하려면
floor(a*100+0.5)/100 와 같이 floor 함수를 이용해주면 됩니다.

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int N,K;
double a[100001];
int main(){
    scanf("%d%d",&N,&K);
    for(int i=1;i<=N;i++) scanf("%lf",&a[i]);
    sort(a+1,a+N+1);
    double sum=0;
    for(int i=K+1;i<=N-K;i++){
        sum+=a[i];
    }
    double t = sum / (N-2*K);
    printf("%.2lf\n",floor(t*100+0.5)/100);
    for(int i=1;i<=K;i++){
        a[i]=a[K+1];
        a[N-i+1] = a[N-K];
    }
    sum=0;
    for(int i=1;i<=N;i++) sum+=a[i];
    t = sum / N;
    printf("%.2lf",floor(t*100+0.5)/100);    
}

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

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

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

[풀이]
각 학생의 반 정보를 a[1001][5] 배열에 저장한 뒤,
0~4 학년 순서로 순회하면서
이중 for문을 이용해 각 학생과 같은 반이었던 학생을 set에 저장을 해줍니다.
set을 이용하는 이유는 a,b가 1학년때 같은 반이었는데 3학년때 또 같은반이 된다고
a와 같은 반이었던 학생이 추가되는 것이 아니기 때문입니다.

#include <cstdio>
#include <set>
#include <vector>
using namespace std;
int N,a[1001][5],mi,mv;
set<int> same[1001];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        for(int j=0;j<5;j++){
            int p;
            scanf("%d",&p);
            a[i][j]=p;
        }
    }
    for(int i=0;i<5;i++){
        for(int j=0;j<N;j++){
            for(int k=0;k<N;k++){
                if(j!=k&&a[j][i]==a[k][i]) same[j].insert(k);
            }
        }
    }
    for(int i=0;i<N;i++){
        if(same[i].size()>mv){
            mv=same[i].size();
            mi=i;
        }
    }
    printf("%d",mi+1);
}

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

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

[난이도] Silver1
[유형] DP

[풀이]
자리를 바꿀 때는 인접한 두 위치의 자리만 바꿀 수 있습니다.
예를 들어 1 2 3 이 있을 때, 세 숫자 모두 자리가 바뀌려면 3 1 2 가 되어야 하는데
3이 원래 위치에서 2만큼 떨어지게 되므로 조건을 만족하지 못하게 됩니다.

그러므로 결국 VIP석이 없는 연속된 자리가 M개 있을 때, 앉을 수 있는 경우의 수는
인접한 두 자리의 쌍을 고르는 경우의 수가 됩니다.

경우의 수가 너무 많으므로 다이나믹 프로그래밍을 이용해야 합니다.

DP[i] : 를 i개의 연속된 자리에서 앉을 수 있는 경우의 수
위와 같이 정의 했을 때,
i) 1번째 자리를 바꾸지 않은 경우
1번째 자리를 제외하고 나머지 i-1개의 자리에 대해서 DP[i-1]을 구해줘야 합니다.

ii) 1,2번째 자리를 바꾼 경우
1,2번째 자리를 제외하고 나머지 i-2개의 자리에 대해서 DP[i-2]를 구해줘야 합니다.

i,ii 두 경우의 수를 더한 것이 DP[i] 이므로
점화식은 DP[i] = DP[i-1] + DP[i-2] 인 것을 알 수 있습니다.

DP[1]~DP[N]을 미리 구해놓고
VIP 좌석간 사이에 연속된 좌석에 앉을 수 있는 경우의 수는 위의 DP 값들로 구하면 됩니다.
각 구간의 값들 곱해주면 총 경우의 수가 됩니다.

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int N,M,dp[41],ans=1;
int sol(int n){
    if(n<=1) return 1;
    int& ret = dp[n];
    if(ret!=-1) return ret;
    ret=sol(n-1)+sol(n-2);
    return ret;
}
int main(){
    vector<int> v;
    scanf("%d%d",&N,&M);
    v.push_back(0);
    for(int i=0;i<M;i++) {
        int t;
        scanf("%d",&t);
        v.push_back(t);
    }
    v.push_back(N+1);
    memset(dp,-1,sizeof(dp));
    sol(N);
    for(int i=1;i<v.size();i++){
        int a = sol(v[i]-v[i-1]-1);
        if(a>0) ans*=a;
    }
    printf("%d",ans);
}

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

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

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

[풀이]
우선 입력을 받으면서 가장 높은 기둥의 높이 mv를 미리 구해줍니다.
그 뒤, 제일 좌측 부터 확인하면서 지금까지 확인한 기둥 중 가장 높은 기둥의 높이 cur을 유지하면서
cur보다 작은 기둥은 모두 cur로 업데이트해주고, cur보다 큰 기둥이 나타나면 cur을 이 기둥의 높이로 업데이트 해줍니다.
계속 위와 같이 진행하다가 가장 높은 기둥 mv가 나타나면 이 기둥의 index를 l로 저장하고 위 과정을 멈춰줍니다.

우측 방향에서도 위와 동일하게 진행해주고 처음 만난 가장 높은 기둥의 index를 r로 저장해줍니다.

위 과정에서 업데이트한 기둥의 합과 mv*(r-l+1) 를 더해주면 전체 면적이 됩니다.

#include <cstdio>
int N,a[1001],ans,l,r,mv;
int main(){
    scanf("%d",&N); 
    for(int i=0;i<N;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        a[u]=v;
        if(v>mv) mv=v;
    }
    int cur=0;
    for(int i=1;i<=1000;i++){
        if(a[i]==mv) {
            l=i;
            break;
        }
        if(a[i]>cur) cur=a[i];
        ans+=cur;
    }
    cur=0;
    for(int i=1000;i>=0;i--){
        if(a[i]==mv) {
            r=i;
            break;
        }
        if(a[i]>cur) cur=a[i];
        ans+=cur;
    }
    printf("%d",ans+mv*(r-l+1));
}

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

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

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

[풀이]
모든 경우의 수를 다 해보면 됩니다. 5개중 더할 3개의 숫자를 고르는 것보다
2개의 숫자를 골라서 전체 합에서 빼주는 것이 편합니다.

#include <cstdio>
#include <string>
int N,a[5],mv,mi;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        int sum=0;
        for(int j=0;j<5;j++) {
            scanf("%d",&a[j]);
            sum+=a[j];
        }
        for(int j=0;j<4;j++){
            for(int k=j+1;k<5;k++){
                int s = sum-a[j]-a[k];
                if(s%10>=mv){
                    mv=s%10;
                    mi=i;
                }
            }
        }
    }
    printf("%d",mi+1);
}

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

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

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

[풀이]
문자열 8개에 대한 약속을 미리 저장해놓고,
입력 문자열을 6개씩 잘라서 어떤 문자열에 매칭되는지 일일히 확인해보면 됩니다.

#include <iostream>
#include <string>
using namespace std;
int N;
string s,sen[] = {"000000","001111","010011","011100","100110","101001","110101","111010"};
int cmp(string v,int i){
    int ret=0;
    for(int j=0;j<6;j++){
        if(sen[i][j]!=v[j]) ret++;
    }
    return ret;
}
int main(){
    cin >> N >> s;
    string ans;
    for(int i=0;i<N;i++){
        string t = s.substr(i*6,6);
        bool ok=0;
        for(int j=0;j<8;j++){
            if(cmp(t,j)<=1) {
                ok=1;
                ans+=('A'+j);
                break;
            }
        }
        if(!ok) {
            cout << i+1;
            return 0;
        }
    }
    cout << ans;
}

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

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

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

[풀이]
가장 큰 변이 나머지 두 변의 합보다 작으면 삼각형을 무조건 만들 수 있습니다.

#include <cstdio>
int N,ans;
int main(){
    scanf("%d",&N);
    for(int i=1;i<N;i++){
        for(int j=i;j<N;j++){
            int k=N-i-j;
            if(j>k) break;
            if(i+j>k) ans++;
        }
    }
    printf("%d",ans);
}

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

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

[난이도] Silver3
[유형] 시뮬레이션

[풀이]
문제의 주어진 조건대로 시뮬레이션 해주면 됩니다.

#include <cstdio>
int N,a[101],k;

void sol1(int n){
    for(int i=n;i<=N;i+=n){
        a[i]=1-a[i];
    }
}
void sol2(int n){
    int k=0;
    for(int i=1;i<=N/2;i++){
        if(n-i<1||n+i>N||a[n-i]!=a[n+i]) break;
        k=i;
    }
    for(int i=n-k;i<=n+k;i++){
        a[i]=1-a[i];
    }
}

int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&a[i]);
    scanf("%d",&k);
    while(k--){
        int p,m;
        scanf("%d%d",&p,&m);
        if(p==1){
            sol1(m);
        }else{
            sol2(m);
        }
    }
    for(int i=1;i<=N;i++){
        printf("%d ",a[i]);
        if(i%20==0) puts("");
    }
}

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