프로그래밍

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

[난이도] Gold3
[유형] DP

[풀이]
나중에..

#include <cstdio>
#include <cstring>
using ll = long long;
using namespace std;
int N,sum[100001],base,cnt;
ll dp[5];
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) {
        int v;
        scanf("%d",&v);
        sum[i]=sum[i-1]+v;
        if(sum[i]==0) cnt++;
    }
    if(sum[N]==0){
        if(cnt<4) puts("0");
        else printf("%lld",(ll)(cnt-1)*(cnt-2)*(cnt-3)/6);
        return 0;
    }
    if(sum[N]%4){
        puts("0");
        return 0;
    }
    base=sum[N]/4;

    dp[0]=1;
    for(int i=1;i<N;i++){
        if(sum[i]%base) continue;
        int j=sum[i]/base;
        if(j==0 || j>3) continue;
        dp[j]+=dp[j-1];
    }
    printf("%lld",dp[3]);
}

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

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

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

[풀이]
vector 두개를 선언하여 짝수번째 수들만 1개만 남을 때까지 복사해주면 됩니다.

#include <cstdio>
#include <vector>
using namespace std;
int N;
vector<int> v1,v2;
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) v1.push_back(i);
    while(v1.size()!=1){
        v2.clear();
        for(int i=1;i<v1.size();i+=2) v2.push_back(v1[i]);
        v1=v2;
    }
    printf("%d",v1.front());
}

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

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

[난이도] Silver3
[유형] Greedy

[풀이]
P인 점을 기준으로 i-K~i+K 만큼을 확인하여 햄버거가 있으면 그 햄버거를 invalid 처리하고
정답에 1을 추가해주면 됩니다.

#include <iostream>
#include <string>
using namespace std;
int N,K,ans;
string s;
int main(){
    cin >> N >> K >> s;
    for(int i=0;i<N;i++){
        if(s[i]=='P'){
            for(int j=i-K;j<=i+K && j<N;j++){
                if(j<0) continue;
                if(s[j]=='H'){
                    ans++;
                    s[j]='O';
                    break;
                }
            }
        }
    }
    printf("%d",ans);
}

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

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

[난이도] Silver5
[유형] Greedy

[풀이]
N을 1,2,3...,K 와 같이 등차수열 형태로 할당이 가능한 경우는 답이 K-1로 최적인 경우입니다.

1~K의 합인 K(K+1)/2 보다 N이 큰 경우에는
큰 수부터 1을 할당해주면 됩니다.
예를 들어
N이 13이고 K가 4일 때,
1,2,3,4 -> 10개를 사용했고 3개가 남았습니다.
1,3,4,5 -> 3개를 큰 수부터 차례로 1씩 할당하여 답은 K = 4입니다.

만약 K가 15라면
2,3,4,5 로 할당 하는 것이 가능하여 답은 K-1 = 3이 됩니다.

이와 같이 N-K(K+1)/2 가 K로 나누어 떨어지는 경에 답은 K-1이 되고,
아닌 경우에는 가장 큰 값에 1을 무조건 더해주어야 하므로 답은 K가 됩니다.

#include <cstdio>
using namespace std;
int N,K,ans;
int main(){
    scanf("%d%d",&N,&K);
    int sum=K*(K+1)/2;
    if(sum>N){
        puts("-1");
        return 0;
    }
    int a = N-sum;
    if(a%K) printf("%d",K);
    else printf("%d",K-1);
}

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

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

[난이도] Gold2
[유형] DP

[풀이]
val[i] : val(X) = N을 만족하는 올바른 괄호 문자열 중에서 dmap(X) 값이 최소인 X

val[i]가 될 수 있는 후보 문자열은
괄호를 감싸는 연산으로 만든
"1" + val[i/2] + "2" (소괄호)
"3" + val[i/3] + "4" (중괄호)
"5" + val[i/5] + "6" (대괄호)
와
concatenation 으로 만든
val[i-j]+val[j] (1<= j < i) 가 있습니다.

이들 중 최솟값을 val[i]로 업데이트 해주면 되는데
최솟값을 정수로 비교하려면 정수 범위를 넘어가버려서 비교가 불가합니다..
그러므로 string 상태에서 비교를 해야합니다.
string 숫자 비교시
12221 보다 344가 크다고 판단하기 때문에
우선 숫자 string의 크기부터 비교해주어야 합니다.

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
int tc,N;
string val[1001],cvt="0(){}[]";
string check(string a,string b){
    if(b=="-1") return a;
    if(a.size() < b.size()) return a;
    if(a.size() > b.size()) return b;
    return min(a,b);
}
void sol(){
    for(int i=1;i<=1000;i++) val[i]="-1";
    val[1]="12";
    val[2]="34";
    val[3]="56";
    for(int i=4;i<=1000;i++){
        string s;
        if(i%2==0) val[i]=check("1"+val[i/2]+"2",val[i]);
        if(i%3==0) val[i]=check("3"+val[i/3]+"4",val[i]);
        if(i%5==0) val[i]=check("5"+val[i/5]+"6",val[i]);
        for(int j=1;j<i;j++) {
            val[i] = check(val[i-j]+val[j],val[i]);
        }
    }
}
int main(){
    cin >> tc;
    sol();
    while(tc--){
        cin >> N;
        for(auto c : val[N]) {
            cout << cvt[c-'0'];
        }
        cout <<'\n';
    }
}

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

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

[난이도] Gold5
[유형] DFS

[풀이]
N이 50이고 k가 1일 때,
k를 사용해서 모든 타일을 6개의 모양으로 바꿔보고 dfs를 하는 방식의 브루트포스로 풀게 되면
O(50*50*6*50*50) 으로 시간초과가 발생할 것으로 생각되지만
dfs를 이용해 실제 경로 탐색을 할 때 각 타일에서 갈 수 있는 다음 타일은 한개밖에 없기 때문에 많은 경로가
가지치기 될 것으로 기대되어 실제로 O(50*50) 만큼의 시간이 발생하지 않습니다.

그러므로 모든 타일을 바꿔는 브루트포스 방식으로 문제 해결이 가능합니다.

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int dy[4]={-1,0,1,0},dx[4]={0,-1,0,1};
int line[6][4]={{0,0,1,1},{0,1,1,0},{1,0,0,1},{1,1,0,0},{1,0,1,0},{0,1,0,1}};
int N,k,board[52][52],visit[52][52];
int match(int i){
    if(i<2) return i+2;
    return i-2;
}
int dfs(int y,int x){
    if(y==N-1&&x==N-1){
        if(board[y][x]==2||board[y][x]==5) return 1;
        return -1;
    }
    if(y==0&&x==0){
        if(board[y][x]%2==0) return -1;
    }
    visit[y][x]=1;
    for(int i=0;i<4;i++){
        int ny=y+dy[i],nx=x+dx[i];
        int m = match(i);
        if(ny<0||nx<0||ny>=N||nx>=N||!line[board[y][x]][i]||!line[board[ny][nx]][m]||visit[ny][nx]) continue;
        int ret = dfs(ny,nx);
        if(ret==-1) return -1;
        return ret+1;
    }
    return -1;
}
int main(){
    scanf("%d%d",&N,&k);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            scanf("%d",&board[i][j]);
        }
    }
    int ans=9e8;
    if(k){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                int t = board[i][j];
                for(int k=0;k<6;k++){
                    if(t!=k) {
                        board[i][j]=k;
                        memset(visit,0,sizeof(visit));
                        int ret = dfs(0,0);
                        if(ret!=-1) ans=min(ans,ret);
                    }
                }
                board[i][j]=t;
            }
        }       
    }else ans=dfs(0,0);
    printf("%d",ans == 9e8 ? -1 : ans);
}

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

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

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

[풀이]
모든 숫자에 대해 직접 확인해주면 됩니다.

#include <cstdio>
#include <string>
using namespace std;
int N,ans;
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        auto s = to_string(i);
        int sum=0;
        for(auto c : s) sum+=c-'0';
        if(i%sum==0) ans++;
    }
    printf("%d",ans);
}

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

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

[난이도] Silver1
[유형] Greedy

[풀이]
최종 볼의 상태는 모든 B가 왼쪽, 모든R이 오른쪽인 상태이거나,
R이 왼쪽, 모든 B가 오른쪽인 상태 둘중에 하나입니다.

각 케이스에서 해당 상태를 만드는 경우에는 R을 움직이는 경우, B를 움직이는 경우 두가지가 있습니다.
결국 총 4가지 케이스인데 이것을 각각 해보면 됩니다.

예를 들어 (B~)(R~) 상태를 R을 움직여서 만들려면 이미 오른쪽 끝에 있는 R들을 제외하고 나머지 R들을
1회 움직여서 오른쪽에 붙혀줘야 합니다.
즉 오른쪽 끝에 있는 R을 제외한 모든 R의 개수를 세주면 됩니다.

위 과정을 4가지 케이스에 대해 각각 해줘서 그중 최솟값을 답으로 출력해주면 됩니다.
여러가지 방법이 있겠지만 저는
이미 뭉쳐있는 공들을 pair vector를 이용해 하나의 묶음으로 묶어주었습니다.
예를 들어 RRBRRRBRRRR 이 있을 때,
{ {'R',2} , {'B',1} , {'R',3} , {'B',1} , {'R',4} } 와 같이 vector에 저장하면
모든 R을 오른쪽으로 보낼 때, index의 마지막인 {'R',4}는 무시하고 {'R',2}, {'R',3} 만 오른쪽으로 보내면 되므로
총 5번의 이동이 필요하게 됩니다.

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<pair<char,int>> v; 
int N;
string s;
int main(){
    cin >> N >> s;
    for(int i=0;i<s.size();i++){
        int j=i;
        int cnt=0;
        for(;j<s.size();j++){
            if(s[i]==s[j]) cnt++;
            else break;
        }
        v.push_back({s[i],cnt});
        i=j-1;
    }
    int ans,rtmp=0,btmp=0;
    for(int i=1;i<v.size();i++){
        auto [col,cnt] = v[i];
        if(col=='R') rtmp+=cnt;
        else btmp+=cnt;
    }
    ans=min(rtmp,btmp);
    rtmp=0,btmp=0;
    for(int i=v.size()-2;i>=0;i--){
        auto [col,cnt] = v[i];
        if(col=='R') rtmp+=cnt;
        else btmp+=cnt;
    }
    ans=min(ans,btmp);
    ans=min(ans,rtmp);
    printf("%d",ans);
}

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