프로그래밍

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://codeforces.com/contest/1598/problem/A

[난이도] Div.2
[유형] BFS

[풀이]
BFS를 이용해 (2,n) 까지 도달이 가능하면 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,mp[3][101];
bool visit[3][101];
int dy[4] = {1,0,1,-1};
int dx[4] = {1,1,0,1};
bool bfs(){

    queue<pair<int,int>> q;
    memset(visit,0,sizeof(visit));

    q.push({1,1});
    visit[1][1]=1;

    while(!q.empty()){

        auto [y,x] = q.front(); q.pop();
        if(y==2&&x==n) return true;
        for(int i=0;i<4;i++){
            int ny=y+dy[i], nx=x+dx[i];
            if(ny<1||nx<1||ny>2||nx>n||visit[ny][nx]||mp[ny][nx]) continue;
            visit[ny][nx]=1;
            q.push({ny,nx}); 
        }
    }
    return false;
}

int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=2;i++)
            for(int j=1;j<=n;j++) scanf("%1d",&mp[i][j]);
        puts(bfs()?"YES":"NO");

    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/RoundEDU115-Div.2/A.cpp

https://codeforces.com/contest/1549/problem/B

[난이도] Div.2
[유형] Greedy

[풀이]
폰의 앞이 비어있다면 무조건 앞으로 전진이 가능하기 때문에
폰이 있으면 앞이 비어있는 폰은 빼주면서 정답에 이 폰의 개수를 더해줍니다.

그다음 좌측 폰부터 확인하면서
좌측 윗쪽에 폰이 있다면 이쪽으로 먼저 보내주고, 없으면 우측 윗쪽에 폰이 있는지 체크해서
폰이 있으면 이쪽으로 보내고 정답에 1을 더해줍니다.

좌측부터 검사하기 때문에 대각선 앞의 적 폰이 있는지 검사할 때 좌측->우측 순으로 검사해서 사용해 주는것이 제일 유리합니다.

#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <map>
using namespace std;
using ll = long long;

int tc,N;
string me,enemy;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> tc;
    while(tc--){
        cin >> N >> enemy >> me;

        int ans=0;
        for(int i=0;i<N;i++){
            if(enemy[i]=='0' && me[i]=='1'){
                ans++;
                me[i]='0';
            }
        }

        for(int i=0;i<N;i++){
            if(me[i]=='0') continue;
            if(i!=0 && enemy[i-1]=='1'){
                ans++;
                continue;
            }
            if(i!=N-1 && enemy[i+1]=='1'){
                ans++;
                enemy[i+1]='0';
            }
        }
        cout << ans << '\n';
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round736-Div.2/B.cpp

https://codeforces.com/contest/1551/problem/C

[난이도] Div.3
[유형] Greedy

[풀이]
n개의 a~e로 이루어진 문자열중에 i개의 문자열을 골랐을 때,
i개의 문자열에 포함된 한 문자(a~e 중 하나)가 나머지 문자들보다 많으면
이것을 Interesting story라고 합니다.

문제에서는 Interesting story를 만들 수 있으면서 i를 최대로 할때의 i값을 출력해야 합니다.

n제한 20만이기때문에 O(n)으로 해결해야 합니다.
Greedy 방식으로 해결이 가능합니다.

예를들어 n이 3이고 아래와 같이 문자열이 주어졌을 때,
bac
aaada
e

일단 알파벳이 a~e 5개밖에 안되기때문에
a가 제일 많은 경우, b가 제일 많은 경우 ... e가 제일 많은 경우
총 5가지의 경우를 가정하여 5가지를 모두 해보는 방식으로 접근합니다.

5가지 경우에 대해 문자열을 가장 많이 선택할 수 있는 경우의 문자열 갯수를 구하고
이중 최댓값이 정답이 됩니다.

bac [ a:1 , 나머지 :2]
aaada [ a:4 , 나머지 :1]
eaeeeb [ a:1 , 나머지 :5]
여기서 a가 가장 많은 경우를 구하면,
3개를 모두 선택하게 되면, a 6개, 나머지 8개로 Interesting story를 만족하지 못합니다.

그러므로 Interesting story가 될때까지 문자열을 한개씩 빼줘야 합니다.
여기서 Interesting story를 만들기 가장 유리한 순서로 문자열을 빼줍니다.
당연하게도 a의 개수보다 나머지 문자의 수가 많을수록 우선적으로 빼주는것이 유리합니다.
그말은 즉, Diff : (a의 개수) - (나머지 문자의 수) 가 작은 수부터 빼주는것이 유리하다는 말이됩니다.

위의 Diff를 각 문자열에 계산해보면
bac -> -1
aaada -> 3
eaeeeb -> -4
이므로 eaeeeb , bac 순으로 빼주는 것이 유리합니다.
vector에 Diff 값들을 넣어주고 정렬하면 순서대로 빼주는 것이 가능합니다.

3개의 문자를 포함했을때는 Diff가 -2였지만 eaeeeb를 빼줌으로써 +2가 됩니다.
전체 Diff가 양수가 되면 Interesting story를 만족하는 것이므로
a가 가장 많은 경우에 선택할 수 있는 문자열의 최대 수는 bac,aaada를 선택한 2가 됩니다.

b,c,d,e에 대해서도 위와 같은 연산을 해주고 이중 최댓값을 선택하면 됩니다.

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
int tc,n;
string arr[200001];

int getCnt(char target){
    int total_diff=0;

    vector<int> diff; // diff
    for(int i=0;i<n;i++){
        int cnt=0;
        for(char c : arr[i]){
            if(c==target){
                cnt++;
            }
        }
        int other = (int)arr[i].size()-cnt;
        diff.push_back(cnt-other);
        total_diff+=(cnt-other);
    }
    sort(diff.begin(),diff.end());
    for(int i=0;i<diff.size();i++){
        if(total_diff>0) {
            return n-i;
        }
        total_diff -= diff[i];
    }
    return 0;
}

void solve(){
    int ret=0;
    for(int i=0;i<5;i++){
        ret=max(ret,getCnt('a'+i));
    }
    cout <<ret<<'\n';
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> tc;
    while(tc--){
        cin >> n; 
        for(int i=0;i<n;i++) cin >> arr[i];
        solve();
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round734-Div.3/C.cpp

https://codeforces.com/contest/1551/problem/B1

[난이도] Div.3
[유형] Greedy

[풀이]
어떤 알파벳이라 2개 이상이라면 레드,그린 각각 1개씩 밖에 들어갈수 없고,
1개만 있는 알파벳들은 어디든지 들어갈 수 있습니다.
이것을 이용하면
답은 (2개 이상인 알파벳의 개수)+(1개만 있는 알파벳의 개수)/2 인것을 알 수 있습니다.

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
int tc,n,a,b,cnt[26];
int main(){
    cin >> tc;
    while(tc--){
        string s;
        cin >> s;
        memset(cnt,0,sizeof(cnt));

        for(char c : s){
            cnt[c-'a']++;
        }

        int ans=0,remain=0;
        for(int i=0;i<26;i++){
            if(cnt[i]>=2) ans++;
            else if(cnt[i]==1) remain++;
        }
        printf("%d\n",ans+remain/2);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round734-Div.3/B-1.cpp

https://codeforces.com/contest/1551/problem/A

[난이도] Div.3
[유형] 수학

[풀이]
1) N%3==0
정확히 1:2로 나눠지므로
답은 c1: N/3 c2 : N/3

2) N%3==1
1 burle만 추가로 필요하므로
답은 c1: (N/3)+1 c2 : (N/3)

3) N%3==2
2 burle만 추가로 필요하므로
답은 c1: (N/3) c2 : (N/3)+1

#include <cstdio>
using namespace std;
int tc,n,a,b;
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&n);
        int k = n/3;
        int mod = n%3;

        a=b=k;
        if(mod==1){
            a++;
        }else if(mod==2){
            b++;
        }
        printf("%d %d\n",a,b);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round734-Div.3/A.cpp

https://codeforces.com/contest/1550/problem/B

[난이도] Div.2
[유형] Greedy

[풀이]
길이 n의 string s가 주어질때 총 지워지는 길이는 n이므로
a*l + b에서 a*l은 결국 a,b 값에 무관하게 정답에 포함되게 됩니다.
Deletion이 일어나는 횟수만큼 b가 추가되게 되므로
b가 음수인지, 양수인지에 따라 deletion 횟수를 최소화 할지, 최대화 해야할지를 정해야합니다.

b가 양수이면
deletion이 최대한 많이 일어나야 하므로 모든 원소를 1씩 지우게 되면
b*n만큼이 정답에 더해지게 됩니다.
결국 a*n+b*n이 b가 양수일때는 cost를 높이는 최적의 값입니다.

b가 음수이면
deletion이 최대한 적게 일어나야 하므로 지울 수 있는 안쪽의 문자열부터 직접 지워봐서 몇번 지워지는지 확인해봅니다.

"000111000111000" -> "000000111000" -> "000000000" -> ""

예를 들어 위와같이 3번 지우면 deletion을 최소로 지울 수 있습니다.

(tutorial을 보면 직접 해보지 않고도 수식으로 간단하게 답을 구하는 풀이가 있습니다.)

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int tc,n,a,b;
int main(){
    cin >> tc;
    while(tc--){
        string s;
        cin >> n >> a >> b >> s;
        int ans = n*a;
        if(b>0){
            ans+=b*n;
        }else if(b<0){

            int l=0;
            while(1){
                bool ok=1;
                int sidx=-1,eidx=-1;
                for(int i=1;i<s.size();i++){
                    if(s[i]!=s[i-1]){
                        sidx=i;
                        eidx=i;
                        ok=0;
                        for(int j=i+1;j<s.size()&&s[j]==s[i];j++){
                            eidx=j;
                        }
                        break;
                    }
                }
                if(ok) {
                    if(!s.empty()) l++;
                    break;
                }
                l++;
                s.erase(sidx,eidx-sidx+1);
            }

            ans+=l*b;
        }
        printf("%d\n",ans);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/RoundEDU111-Div.2/B.cpp

https://codeforces.com/contest/1550/problem/A

[난이도] Div.2
[유형] Greedy

[풀이]

배열을 전부 만들어봐야 하는지, DP로 풀어야하는지 등등 여러 삽질을 하다가
A번 문제인데도 컨테스트중에 풀지 못한 문제입니다. ㅠㅠ

tutorial을 보니 접근을 완전히 잘못 한것을 깨달았습니다.

n이 배열의 모든 원소의 합이라고 할때
n==1 -> [1] : 길이1
n==4 -> [1,3] : 길이2
n==9 -> [1,3,5] : 길이3
n==16 -> [1,3,5,7] : 길이4
...

위와같이 n이 1,2,3,4..의 제곱수이면 최소 배열의 길이가 1씩 늘어남을 알 수 있습니다. (2씩 큰수를 추가하면 되므로)

1 2개
4 3개
9 4개
각 배열의 마지막수를 1씩 감소시켜서 배열을 만들어보면
위와같이 n일때 최소 배열의 길이를 찾을 수 있습니다.

예를 들어 n==10일때를 구해본다면
[1,3,5,7]을 [1,3,5,1]로 바꿔주는 식으로 마지막 수를 1씩 줄여보면 모든 n에 대해서 구할 수 있습니다.

https://github.com/has2/Problem-Solving/blob/master/codeforces/RoundEDU111-Div.2/A.cpp