프로그래밍

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

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

[풀이]
1과 2가 무조건 동시에 사용되어야 하므로, 전체 수열의 합이 3의 배수여야 하고
(전체 수열의 합 / 3) = (물뿌리개를 사용해야 하는 횟수) = (2를 사용해야 하는 횟수) 이므로
1~N 사과나무들의 2로 나눈 몫의 합이 위의 (2를 사용해야 하는 횟수) 이상이어야 합니다.

이것을 만족하지 못하는 조건은 다음과 같이 표현이 가능합니다.
cnt : 2로 나눈 몫의 합
if(sum%3||cnt<sum/3) {
    puts("NO");
    return 0;
}

#include <cstdio>
int N,a[100000],sum,cnt;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        scanf("%d",&a[i]);
        sum+=a[i];
        cnt+=a[i]/2;
    }
    if(sum%3||cnt<sum/3) {
        puts("NO");
        return 0;
    }
    puts("YES");
}

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

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

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

[풀이]
N이 6이므로 최대 칸의 수는 36개입니다.
장애물을 놓을 수 있는 경우의 수는 X인 칸을 vector에 저장해놓고 3중 for문을 이용해
구할 수 있습니다.

세개의 위치의 X를 O로 바꾼 뒤 학생들이 검사를 피할 수 있는지 확인해보면 됩니다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
char board[6][6];
vector<pair<int,int>> p,s;
bool check(){
    for(auto [y,x] : s){
        for(int i=0;i<4;i++){
            int cy=y,cx=x;
            while(cy>=0&&cx>=0&&cy<N&&cx<N&&board[cy][cx]!='O'){
                if(board[cy][cx]=='T') return false;
                cy+=dy[i],cx+=dx[i];
            }
        }   
    }
    return true;
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            scanf(" %c",&board[i][j]);
            if(board[i][j]=='X') p.push_back({i,j});
            if(board[i][j]=='S') s.push_back({i,j});
        }
    }
    int M = p.size();
    for(int i=0;i<M-2;i++){
        for(int j=i+1;j<M-1;j++){
            for(int k=j+1;k<M;k++){
                auto [y1,x1] = p[i];
                auto [y2,x2] = p[j];
                auto [y3,x3] = p[k];
                board[y1][x1] = board[y2][x2] = board[y3][x3] = 'O';
                if(check()) {
                    puts("YES");
                    return 0;
                }
                board[y1][x1] = board[y2][x2] = board[y3][x3] = 'X';
            }
        }
    }
    puts("NO");
}

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

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

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

[풀이]
N 제한이 20밖에 되지 않기 때문에 모든 경우의 수를 해보는 브루트포스 알고리즘으로 해결이 가능합니다.
재귀와 비트마스크를 이용한 방법이 가능한데, 비트마스크를 이용하였습니다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int N,d[20][20],ans=9e8;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++) scanf("%d",&d[i][j]);
    for(int i=0;i<(1<<N);i++){
        vector<int> a(N);
        vector<int> p,q;
        for(int j=0;j<N;j++){
            if(i&(1<<j)) {
                p.push_back(j);
                a[j]=1;
            }
            else q.push_back(j);
        }
        if(p.empty() || q.empty()) continue;
        int t1=0,t2=0;
        for(int j=0;j<p.size();j++){
            for(int k=0;k<p.size();k++){
                t1+=d[p[j]][p[k]];
            }
        }
        for(int j=0;j<q.size();j++){
            for(int k=0;k<q.size();k++){
                t2+=d[q[j]][q[k]];
            }
        }   
        ans=min(ans,abs(t1-t2));
    }
    printf("%d",ans);
}

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

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

[난이도] Gold5
[유형] DP

[풀이]
전형적인 LCS (DP) 문제입니다.

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
string A,B;
int dp[41][41];
pair<int,int> par[41][41];
int main(){
    cin >> A >> B;
    for(int i=0;i<A.size();i++){
        for(int j=0;j<B.size();j++){
            if(A[i]==B[j]) {
                dp[i+1][j+1] = dp[i][j]+1;
                par[i+1][j+1] = {i,j};
            }else{
                if(dp[i+1][j] > dp[i][j+1]){
                    dp[i+1][j+1] = dp[i+1][j];
                    par[i+1][j+1] = {i+1,j};
                }else{
                    dp[i+1][j+1] = dp[i][j+1];
                    par[i+1][j+1] = {i,j+1};                    
                }
            }
        }
    }
    string ans;
    int i=A.size(),j=B.size();
    while(i!=0&&j!=0){
        if(A[i-1] == B[j-1]) ans+=A[i-1];
        auto v = par[i][j];
        i=v.first;
        j=v.second;
    }
    reverse(ans.begin(),ans.end());
    cout << ans;
}

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

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

[난이도] Gold4
[유형] DP

[풀이]
DP[n][k] : n = 현재 돌의 번호, k = 이전에 점프한 칸의 개수
k는 최악의 겨우에도
1+2+3+4+...k=10000
이므로 (k+1)k/2 = 10000 의 식을 이용하면 대략 500은 절대 넘지 않으므로
배열을 DP[10000][500] 으로 설정하여 메모리 초과를 피하였씁니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,M,dp[10001][500],a[10000],inf=9e8;
int sol(int n,int k){
    if(n==N) return 0;
    if(n>N||a[n]) return -1;

    int& ret = dp[n][k];
    if(ret!=-1) return ret;

    ret=inf;
    for(int i=k-1;i<=k+1;i++){
        if(i<1) continue;
        int v = sol(n+i,i);
        if(v==-1) continue;
        ret=min(ret,v);
    }
    if(ret==inf) return ret=-1;
    ret++;
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int v;
        scanf("%d",&v);
        a[v]=1;
    }
    memset(dp,-1,sizeof(dp));
    int ans = sol(2,1);
    if(ans==-1) puts("-1");
    else printf("%d",ans+1);
}

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

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://www.acmicpc.net/problem/2210

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

[풀이]
재귀함수를 이용해서 가능한 모든 경우를 구해주면 됩니다.

#include <cstdio>
#include <set>
#include <string>
#include <cstring>
using namespace std;
int dy[4]={-1,1,0,0},dx[4]={0,0,1,-1},board[5][5],ans;
set<string> st;
void sol(int y,int x,string s){
    if(s.size()==6){
        st.insert(s);
        return;
    }
    for(int i=0;i<4;i++){
        int ny=y+dy[i],nx=x+dx[i];
        if(ny<0||nx<0||ny>=5||nx>=5) continue;
        char c = board[ny][nx]+'0';
        string t;
        t=s+c;
        sol(ny,nx,t);
    }
}
int main(){
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++) scanf("%d",&board[i][j]);
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            string t;
            t+=(board[i][j]+'0');
            sol(i,j,t);
        }
    }
    printf("%d",st.size());
}

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

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

[난이도] Silver2
[유형] 백트래킹

[풀이]
오름차순으로 출력해야 하기 때문에 정렬 후에 백트래킹을 해주면 됩니다.
중복 제거를 위해 set을 이용하였습니다.

#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
int N,M,a[8];
set<vector<int>> st;
vector<int> ans;
void sol(int n){
    if(n==N){
        if(ans.size()==M) {
            if(st.find(ans) == st.end()){
                st.insert(ans);
                for(auto k : ans) printf("%d ",k);
                puts("");
            }
        }
        return;
    }
    ans.push_back(a[n]);
    sol(n+1);
    ans.pop_back();
    sol(n+1);
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    sort(a,a+N);
    sol(0);
}

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