프로그래밍

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

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

[풀이]

문제를 풀어서 해석해보면 결국
M*a+x == N*b+y를 만족하는 a,b가 있는지를 찾는 문제입니다..

M*a == N*b가 되면 종말이며, 이때 M*a,N*b는 M,N의 최소공배수입니다..
즉, a는 lcm(M,N)/M 이상이 될수 없고, b는 lcm(M,N)/N 이상이 될 수 없습니다..

코드상에서 보면 a를 curM 변수, b를 curN 변수로 놓고
curM*M+x == curN*N+y을 만족할때까지
curM,curN을 하나씩 증가시키면서 루프를 돌리면 됩니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int tc,M,N,x,y;
int gcd(int a,int b){
    if(a>b) swap(a,b);
    while(a!=0){
        int c = b%a;
        b=a;
        a=c;
    }
    return b;
}
int sol(){
    int lcm = (M*N)/gcd(M,N);
    int mxM = lcm/M, mxN = lcm/N;
    int curM=0,curN=0;
    while(curM<mxM&&curN<mxN){
        int l = curM*M+x;
        int r = curN*N+y;
        if(l==r) return l;
        if(l>r) curN++;
        else curM++;
    }
    return -1;
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d%d%d",&M,&N,&x,&y);
        printf("%d\n",sol());
    }
}

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

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

[난이도] Silver2
[유형] 문자열

[풀이]
문자열의 최대 길이가 100만이므로 O(N^2)으로는 해결이 불가능합니다.
문자를 한번씩만 확인하는 O(N) 알고리즘으로 해결해야합니다.

일단 string 타입의 search 변수에 찾아야 하는 2*N+1 문자열을 만들어서 저장해놓습니다.
그 뒤, find 함수를 이용하여 입력문자열 s에서 start부터 탐색하여 search를 찾습니다.
만약 search가 없다면 그대로 루프를 종료합니다.
search가 있다면 search가 시작되는 인덱스 idx에서 search의 길이 2*N+1만큼 더한
idx에서 "OI"가 추가로 붙어있는지를 idx 2씩 증가시키며 확인해줍니다.
예를 들어 search가 IOIOI 일때, 어떤 IOIOI를 찾았다면, 그 뒤에 OI가 추가로 붙어있는만큼
search의 개수가 늘어나는 것입니다. (IOIOI(OIOI) <- OIOI가 뒤에 2개 더 붙어있으므로 search가 2개 더 늘어난다)

find를 통해 나온 search에서 몇개의 겹쳐진 search가 추가되는지를 찾아서 정답에 추가하고,
start를 다음 탐색해야하는 index로 옮겨주면서 루프를 진행해줍니다.

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
int N,M,ans;
string s,search;
int main(){
    cin >> N >> M >> s;
    for(int i=0;i<N;i++) search+="IO";
    search+="I";
    int start=0;
    while(start<s.size()){
        int idx=s.find(search,start);
        if(idx==string::npos) break;
        int k=1;
        for(start=idx+2*N+1;start<s.size()-1;start+=2){
            if(s[start]=='O'&&s[start+1]=='I') k++;
            else break;
        }
        ans+=k;
    }
    printf("%d",ans);
}

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

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

[난이도] Silver1
[유형] 우선순위큐

[풀이]
우선순위큐

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val pq = PriorityQueue<Int>()
    var N = readLine().toInt()
    while(N-->0){
        var k = readLine().toInt()
        when(k){
            0 -> {
                var t = 0
                pq.poll()?.let{
                    t+=it
                }
                println(t)
            }
            else -> pq.add(k)
        }
    }
}

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

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

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

[풀이]
몇번 연산이 일어나든 같은 index 위치의 문자들끼리만 교환이 일어나므로
연산 후의 특정 index에 존재하는 a~z의 각 개수는 동일해야합니다.
이것을 이용하면 어떤 문자열이 사라졌는지 찾을 수 있습니다.

1. check[100001][26] 배열을 선언해 0~N-1 번째 위치에 a~z (0~25) 가 각 몇개씩 있는지를 저장해놓습니다.
(만약 i번 위치에 'c'가 있다면 check[i]['c'-'a]++ 를 통해 c 1개가 추가되었다는 것을 기록합니다.)
2. 그 다음에 주어지는 연산이 완료된 N-1개의 문자에 대해 i번 위치에 어떤 문자가 있으면 check[i]['문자'-'a']-- 연산을 통해 연산 뒤에도 해당 문자가 남아있음을 체크합니다.

3. 사라진 문자열의 i번 문자는 check[i][j] (j:0~25 (a~z index)) 중에 1인 문자가 됩니다.

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int tc,N,M;
int check[100001][26];

void solve(){
    memset(check,0,sizeof(check));

    string s,ret;
    for(int i=0;i<N;i++){
        cin >> s;
        for(int j=0;j<M;j++){
            check[j][s[j]-'a']++;
        }
    }

    for(int i=0;i<N-1;i++){
        cin >> s;
        for(int j=0;j<M;j++){
            check[j][s[j]-'a']--;
        }
    }
    for(int i=0;i<M;i++){
        for(int j=0;j<26;j++){
            if(check[i][j]>0){
                ret.push_back(j+'a');
            }
        }
    }
    cout << ret << '\n';
    cout << flush;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> tc;
    while(tc--){
        cin >> N >> M;
        solve();
    }
}

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

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

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

[풀이]
최대 100번의 연산 내에 A배열을 B배열로 만들어야 합니다.
각 루프에서 i:0~N-1 루프를 돌면서 A[i]-B[i]가 가장 작은 값과 큰 값을 찾아서 저장한 뒤
A[i]-B[i]가 작은 A[i]는 +1, 큰 A[i]는 -1 을 해주면
이것이 매 루프마다 정답에 가장 유리한 연산이 됩니다.

100번내에 A=B를 만들 수 있으면 정답을 출력합니다.

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int tc,N,a[100],b[100],INF=987654321;

bool same(){
    for(int i=0;i<N;i++){
        if(a[i]!=b[i]) return false;
    }
    return true;
}
void prt(){
    for(int i=0;i<N;i++){
        printf("%d ",a[i]);
    }
    puts("");
}
void solve(){

    int it=100;
    vector<pair<int,int>> ans;
    while(it--){

        int minDiff=INF,minIdx=-1;
        int maxDiff=-INF,maxIdx=-1;
        bool ok=1;
        for(int i=0;i<N;i++){
            int d = a[i]-b[i];
            if(d!=0) ok=0;
            if(minDiff>d){
                minDiff=d;
                minIdx=i;
            }
            if(maxDiff<d){
                maxDiff=d;
                maxIdx=i;
            }
        }
        if(ok) break;

        a[minIdx]++;
        a[maxIdx]--;
        ans.push_back({maxIdx,minIdx});
    }
    if(same()){
        printf("%d\n",ans.size());
        for(auto p : ans){
            printf("%d %d\n",p.first+1,p.second+1);
        }
    }else{
        puts("-1");
    }
}

int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);
        for(int i=0;i<N;i++) scanf("%d",&a[i]);
        for(int i=0;i<N;i++) scanf("%d",&b[i]);
        solve();
    }
}

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

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

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

[풀이]
Greedy 문제입니다.

a,b 배열의 index를 aidx, bidx로 유지하면서 a[aidx],b[bidx]중 하나를 선택해
ans vector에 추가해주는 식으로 풉니다. 정답이 존재한다면 ans vector의 크기가 n+m이 되어야 합니다.

a[adix],b[bidx] 중에 고르는 기준은 다음과 같습니다..
1) 둘중 0이 있는 경우 무조건 선택한다. 새로운 라인을 추가하는 것은 어떤 경우에도 유리하기 때문
2) 0이 없을때는 k (현재 페이지의 총 라인수) 보다 작거나 같은 값이 있으면 선택한다. 라인을 수정하는 것은
아직 선택되지 않은 것들에 어떤 악영향도 미치지 않으므로

aidx==n , bidx==m이 될때까지 위 과정을 반복하면 ans vector에 최종 정답이 저장됩니다.

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int tc;
int k,n,m,a[301],b[301];
 
void prt(){
    puts("a");
    for(int i=0;i<n;i++) printf("%d ",a[i]);
 
    puts("b");
    for(int i=0;i<m;i++) printf("%d ",b[i]);
}
 
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d%d",&k,&n,&m);
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        for(int i=0;i<m;i++) scanf("%d",&b[i]);
        vector<int> ans;
 
        int aidx=0,bidx=0;
        int it=m+n;
        while(it--){
            if(aidx<n){
                if(a[aidx]==0) {
                    k++;
                    aidx++;
                    ans.push_back(0);
                    continue;
                }
            }
            if(bidx<m){
                if(b[bidx]==0) {
                    k++;
                    bidx++;
                    ans.push_back(0);
                    continue;
                }
            }
 
            if(aidx<n){               
                if(k>=a[aidx]){
                    ans.push_back(a[aidx]);
                    aidx++;
 
                    continue;
                }
            }            
            if(bidx<m){
                if(k>=b[bidx]){
                    ans.push_back(b[bidx]);
                    bidx++;
                    continue;
                }
            }    
        }
        if(ans.size()<m+n) puts("-1");
        else{
            for(int a : ans) printf("%d ",a);
            puts("");
        }
    }
    
}

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