프로그래밍

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

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

[풀이]
두 배열의 겹치는 부분은 Bi,j = Ai,j + Ai-X,j-Y 와 같으므로
겹치는 부분의 A배열의 값은 A[i][j] = B[i][j] - A[i-X][j-Y] 의 식으로 구할 수 있습니다.
A[0][0] 부터 구하기 시작하면 A[i-X][j-Y]는 이미 구해져 있다는 것이 보장되기 때문에
위의 식에서 A[i-X][j-Y]이 없어서 못구하는 상황은 발생하지 않습니다.

#include <cstdio>
int H,W,X,Y,B[700][700],A[300][300];
int main(){
    scanf("%d%d%d%d",&H,&W,&X,&Y);
    for(int i=0;i<H+X;i++)
        for(int j=0;j<W+Y;j++) scanf("%d",&B[i][j]);
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(i>=X && j>=Y) A[i][j] = B[i][j] - A[i-X][j-Y];
            else A[i][j] = B[i][j];
            printf("%d ",A[i][j]);
        }
        puts("");
    }
}

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

https://school.programmers.co.kr/learn/courses/30/lessons/118667

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

[풀이]
전체 합의 절반 값이 t일 때, queue1의 값을 t로 만들면 됩니다.
실제로 큐 두개를 선언하여 queue1,queue2에 넣고 현재 queue1 값들의 합을 sum이라고 했을 때,
sum의 값이 t보다 크면 queue1 에서 pop, t보다 작으면 queue2에서 pop 하는 방식으로 sum이 t가 될때까지 진행해줍니다.
최대 연산 횟수는 queue1,queue2의 초기 사이즈를 N이라고 했을 때,
queue1의 값을 모두 queue2로 옮겼다가 queue2에 있는 값을 다시 queue1으로 옮기는 경우 이므로 N+2*N = 3*N 이 됩니다.
연산 과정에서 무한히 반복될 수 있으므로 최대 3*N만큼만 루프를 돌려줍니다.

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
using ll = long long;
ll sum,sum2;
queue<int> q1,q2;
int N;
int solution(vector<int> a, vector<int> b) {
    for(int i=0;i<a.size();i++){
        sum+=a[i];
        sum2+=b[i];
        q1.push(a[i]);
        q2.push(b[i]);
    }

    if((sum+sum2)%2)return -1;
    ll t = (sum+sum2)/2;

    int i=0,j=0,ans=0,n=a.size()*3;
    while(n--){
        if(sum>t){
            ans++;
            int v = q1.front();
            sum-=v;
            q2.push(v);
            q1.pop();
        }else if(sum<t){
            ans++; 
            int v = q2.front();
            sum+=v;
            q1.push(v);
            q2.pop();            
        }else{
            return ans;
        }
    }
    return -1;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/두_큐_합_같게_만들기.cpp

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

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

[풀이]
지문에 적힌대로 구현하는 문제이므로 풀이법은 여러개 입니다.
저는 구조체에 인접한 칸에 좋아하는 학생의 수, 인접한 칸에 빈칸, (y,x) 좌표를 저장한 뒤
comparator 3개를 구현한 정렬을 이용해서 1,2,3 조건에 대한 처리를 해주었습니다.

#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int N,board[21][21],ans;
set<int> fav[401];
int dy[4]={-1,1,0,0};
int dx[4]={0,0,1,-1};
struct P{
    int f,e;
    pair<int,int> pos;
};
bool cmp1(P& u,P& v){
    return u.f > v.f; 
}
bool cmp2(P& u,P& v){
    return u.e > v.e; 
}
bool cmp3(P& u,P& v){
    return u.pos < v.pos; 
}
void sol(int n){
    vector<P> v;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(board[i][j]) continue;
            int f=0,e=0;
            for(int k=0;k<4;k++){
                int ny=i+dy[k],nx=j+dx[k];
                if(ny<0||nx<0||ny>=N||nx>=N) continue;
                if(board[ny][nx]==0) e++;
                else if(fav[n].find(board[ny][nx])!=fav[n].end())f++;
            }
            v.push_back({f,e,{i,j}});
        }
    }
    sort(v.begin(),v.end(),cmp1);
    vector<P> v2;
    for(auto p : v){
        if(v[0].f!=p.f) break;
        v2.push_back(p);
    }
    if(v2.size()==1) {
        board[v2[0].pos.first][v2[0].pos.second] = n;
        return;
    }
    sort(v2.begin(),v2.end(),cmp2);
    vector<P> v3;
    for(auto p : v2){
        if(v2[0].e!=p.e) break;
        v3.push_back(p);
    }    
    if(v3.size()==1) {
        board[v3[0].pos.first][v3[0].pos.second] = n;
        return;
    }
    sort(v3.begin(),v3.end(),cmp3);
    board[v3[0].pos.first][v3[0].pos.second] = n;
}

int main(){
    scanf("%d",&N);
    for(int i=0;i<N*N;i++){
        int n,v;
        scanf("%d",&n);
        for(int j=0;j<4;j++) {
            scanf("%d",&v);
            fav[n].insert(v);
        }
        sol(n);
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            int cnt=0;
            for(int k=0;k<4;k++){
                int ny=i+dy[k],nx=j+dx[k];
                if(ny<0||nx<0||ny>=N||nx>=N) continue;
                if(fav[board[i][j]].find(board[ny][nx])!=fav[board[i][j]].end()) cnt++;
            }
            if(cnt==1) ans+=1;
            if(cnt==2) ans+=10;
            if(cnt==3) ans+=100;
            if(cnt==4) ans+=1000;
        }        
    }
    printf("%d",ans);
}

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

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

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

[풀이]
300초, 60초, 10초짜리 버튼 순으로 많이 사용하는 것이 유리하므로
T를 300으로 나눈 몫이 300초 버튼을 가장 많이 사용할 수 있는 갯수이고,
T를 300으로 나눈 나머지가 300초 버튼을 사용하고 남은 시간입니다.
이를 다시 60초, 10초에 대해서 연산해주어서 각 버튼을 몇번 사용하는지 구하면 됩니다.
만약 T가 10으로 나누어지지 않는다면 주어진 버튼으로 구할 수 없으므로 -1을 출력해주면 됩니다.

#include <cstdio>

int T;
int main(){
    scanf("%d",&T);
    if(T%10) {
        puts("-1");
        return 0;
    }
    printf("%d ",T/300);
    T%=300;
    printf("%d ",T/60);
    T%=60;
    printf("%d ",T/10);
    T%=10;
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Bronze4/10162.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/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