프로그래밍

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

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

[풀이]
S에서 T를 만드려고 하면 모든 문자에서 두가지 연산을 다 해봐야 하기 때문에 시간초과가 발생합니다.
역으로 T에서 S로 원복시키는 방식으로 하면 각 연산을 적용할 수 없는 경우가 생기기 때문에
많은 케이스가 가지치기 됩니다.
그러므로 재귀함수로 T에서 S를 만들 때 가능한 모든 경우의 수를 구해서 체크해주면 됩니다.

#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
string S,T;
bool ok;
void sol(string s){
    if(s==S){
        ok=1;
        return;
    }
    if(s.size()<=S.size()) return;
    if(s.front()=='B'){
        string tmp = s;
        reverse(tmp.begin(),tmp.end());
        tmp.pop_back();
        sol(tmp);
    }
    if(s.back()=='A'){
        s.pop_back();
        sol(s);
    }
}
int main(){
    cin >> S >> T;
    sol(T);
    cout << ok;
}

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

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

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

[풀이]
N이 15밖에 되지 않으므로 모든 경우의 수를 재귀함수를 이용해 다 해보면 됩니다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct P{
    int p,f,s,v,c;
};
int N,mp,mf,ms,mv,ansv=9e8;
P a[15];
vector<int> vec,ans;
void sol(int n,int p,int f,int s,int v,int c){
    if(n==N){
        if(p>=mp&&f>=mf&&s>=ms&&v>=mv){
            if(ansv>c){
                ans=vec;
                ansv=c;
            }else if(ansv==c && ans>vec){
                ans=vec;
                ansv=c;                
            }
        }
        return;
    }
    sol(n+1,p,f,s,v,c);
    vec.push_back(n);
    sol(n+1,p+a[n].p,f+a[n].f,s+a[n].s,v+a[n].v,c+a[n].c);
    vec.pop_back();
}
int main(){
    scanf("%d%d%d%d%d",&N,&mp,&mf,&ms,&mv);
    for(int i=0;i<N;i++){
        scanf("%d%d%d%d%d",&a[i].p,&a[i].f,&a[i].s,&a[i].v,&a[i].c);
    }
    sol(0,0,0,0,0,0);
    if(ansv==9e8){
        puts("-1");
        return 0;
    }
    printf("%d\n",ansv);
    for(auto k : ans) printf("%d ",k+1);
}

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

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

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

[풀이]
N 제한이 5밖에 되지 않으므로 백트래킹 함수를 통해 모든 경우의 경로를 다 해보면 됩니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,dy[2]={1,0},dx[2]={0,1},minv=1e9,maxv=-1e9;
char a[5][5];
void sol(int y,int x,int val){
    if(y==N-1&&x==N-1){
        minv=min(minv,val);
        maxv=max(maxv,val);
        return;
    }
    for(int i=0;i<2;i++){
        int ny=y+dy[i],nx=x+dx[i];
        if(ny>=N||nx>=N) continue;
        int nv = val;
        if(a[y][x]=='-'){
            nv-=a[ny][nx]-'0';
        }else if(a[y][x]=='+'){
            nv+=a[ny][nx]-'0';
        }else if(a[y][x]=='*') {
            nv*=a[ny][nx]-'0';
        }
        sol(ny,nx,nv);
    }
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++) scanf(" %c",&a[i][j]);
    sol(0,0,a[0][0]-'0');
    printf("%d %d",maxv,minv);
}

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

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

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

[풀이]
핀의 개수가 최대 8개밖에 되지 않기 때문에 핀의 위치를 저장한 set, 보드의 상태를 저장한 vector를
파라미터로 하는 백트래킹 함수를 짜주면 완전탐색으로 답을 구할 수 있습니다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
int tc,dy[4]={-1,1,0,0},dx[4]={0,0,1,-1},ans,ansc;
void sol(vector<string> b,set<pair<int,int>> p,int cnt){
    if(ans>p.size()){
        ans=p.size();
        ansc=cnt;
    }else if(ans==p.size() && ansc>cnt) ansc=cnt;
    for(auto [y,x] : p){
        for(int i=0;i<4;i++){
            int ny=y+dy[i],nx=x+dx[i];
            if(ny<0||nx<0||ny>=5||nx>=9||b[ny][nx]!='o') continue;
            int nny=ny+dy[i],nnx=nx+dx[i];
            if(nny<0||nnx<0||nny>=5||nnx>=9||b[nny][nnx]!='.') continue;
            auto tb=b;
            auto tp=p; 
            tb[y][x]='.';
            tb[ny][nx]='.';
            tb[nny][nnx]='o';
            tp.insert({nny,nnx});
            tp.erase({ny,nx});
            tp.erase({y,x});
            sol(tb,tp,cnt+1);
        }
    }
}
int main(){
    cin >> tc;
    while(tc--){
        ans=9e8,ansc=9e8;
        vector<string> board;
        set<pair<int,int>> p;
        for(int i=0;i<5;i++){
            string s;
            cin >> s;
            board.push_back(s);
            for(int j=0;j<s.size();j++){
                if(s[j]=='o') p.insert({i,j});
            }
        }
        sol(board,p,0);
        cout << ans << " " << ansc << "\n";
    }
}

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

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

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

[풀이]
직사각형 3개로 나눌 수 있는 모양은 총 6가지가 나옵니다.
수평, 혹은 수직으로 3개로 나누는 2개 이외에,
ㅏ ㅓ ㅜ ㅗ 모양의 4가지 모양이 더 있을 수 있다는 것을 주의해야 합니다.
N,M 제한이 50밖에 되지 않으므로,
2중, 3중 for문을 적절히 활용해서 구간을 나누어 브루트포스로 구해주면 됩니다.

#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;
int N,M;
ll a[50][50];
ll sol(int sy,int sx,int ey,int ex){
    ll sum=0;
    for(int i=sx;i<=ex;i++)
        for(int j=sy;j<=ey;j++)
            sum+=a[j][i];
    return sum;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) scanf("%1lld",&a[i][j]);

    ll ans=0;
    for(int i=0;i<N-2;i++)
        for(int j=i+1;j<N-1;j++)
            ans=max(ans,sol(0,0,i,M-1)*sol(i+1,0,j,M-1)*sol(j+1,0,N-1,M-1));

    for(int i=0;i<M-2;i++)
        for(int j=i+1;j<M-1;j++)
            ans=max(ans,sol(0,0,N-1,i)*sol(0,i+1,N-1,j)*sol(0,j+1,N-1,M-1));

    for(int i=0;i<N-1;i++){
        for(int j=0;j<M-1;j++) ans=max(ans,sol(0,0,i,M-1)*sol(i+1,0,N-1,j)*sol(i+1,j+1,N-1,M-1));
        for(int j=0;j<M-1;j++) ans=max(ans,sol(i+1,0,N-1,M-1)*sol(0,0,i,j)*sol(0,j+1,i,M-1));
    }
    for(int i=0;i<M-1;i++){
        for(int j=0;j<N-1;j++) ans=max(ans,sol(0,0,N-1,i)*sol(0,i+1,j,M-1)*sol(j+1,i+1,N-1,M-1));
        for(int j=0;j<N-1;j++) ans=max(ans,sol(0,i+1,N-1,M-1)*sol(0,0,j,i)*sol(j+1,0,N-1,i));
    }
    printf("%lld",ans);
}

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

https://programmers.co.kr/learn/courses/30/lessons/84512

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

[풀이]
재귀 함수를 이용해 사전순으로 문자열을 만들어보면 됩니다.

#include <string>
#include <vector>
using namespace std;
char mp[5] = {'A','E','I','O','U'};
int ans;
int sol(string str,string& word){
    ans++;
    if(str==word) return ans-1;
    if(str.size()>=5) return 0;
    for(int i=0;i<5;i++) {
        int ret=sol(str+mp[i],word);
        if(ret) return ret;
    }
    return 0;
}
int solution(string word) {
    return sol("",word);
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/위클리_챌린지.cpp