프로그래밍

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

[난이도] Gold5
[유형] 에라토스테네스의 체

[풀이]
N의 최댓값이 100만보다 넉넉하게 큰 수인 500만까지 에라토스테네스의 체를 이용해 어느것이 소수인지
배열에 체크해준다.
그 뒤 N보다 큰 소수중에 가장 작은 팰린드롬인 수를 찾으면 시간내에 해결이 가능하다.

#include <cstdio>
#include <string>
using namespace std;
int N;
const int mxN=5e6;
bool np[mxN];
bool check(int n){
    string s = to_string(n);
    int sz = s.size();
    for(int i=0;i<sz/2;i++){
        if(s[i]!=s[sz-1-i]) return 0;
    }
    return 1;
}
int main(){
   scanf("%d",&N);
   np[1]=1;
   for(int i=2;i<mxN;i++){
       if(np[i]) continue;
       for(int j=i+i;j<mxN;j+=i) np[j]=1;
   }
   for(int i=2;i<mxN;i++){
       if(i>=N && !np[i] && check(i)){
           printf("%d",i);
           return 0;
       }
   }
} 

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

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

[난이도] Gold5
[유형] Greedy

[풀이]
N개의 센서를 위치 기준으로 정렬한 뒤, 센서들 사이의 거리 N-1개를 배열에 넣은 후 다시 정렬을 해준다.
그 뒤 거리가 큰 K-1개의 거리를 뽑아서 그 구간을 제거하면 총 K개의 집중국을 설치한 것과 같은 효과를 가진다.
그러므로 뽑은 K-1개의 거리들을 총 구간에서 빼주면 정답이 된다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,K,a[10000];
int main(){
    scanf("%d%d",&N,&K);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    sort(a,a+N);
    int ans = a[N-1]-a[0];
    for(int i=1;i<N;i++) a[i-1] = a[i]-a[i-1]; 
    sort(a,a+N-1);
    for(int i=N-2;i>=N-K && i>=0 ;i--) ans-=a[i];
    printf("%d",ans);
} 

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

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

[난이도] Gold5
[유형] 투포인터

[풀이]
가장 작은 수의 index 0을 l, 가장 큰 수의 index N-1을 r로 설정한 뒤
a[l]+a[r]의 합이 양수이면 r--을 해주어 0과 가깝게 해주고
음수이면 l++을 해주어 0과 가깝게 해주는 방식으로 0과 가까운 후보들을 모두 훑을 수 있다.

#include <cstdio>
#include <cmath>
using namespace std;
int N,a[100000];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    int l=0,r=N-1,ans=2e9+1;
    int al=l,ar=r;
    while(l<r){
        int v = a[l]+a[r];
        if(abs(v)<ans){
            al=l;
            ar=r;
            ans=abs(v);
        }
        if(v==0) break;
        else if(v>0) r--;
        else l++;
    }
    printf("%d %d",a[al],a[ar]);
} 

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

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

[난이도] Gold5
[유형] 그래프

[풀이]
vector를 이용해 인접리스트를 만든 후 root에서부터 dfs로 순회를 해준다.
현재 노드가 삭제된 노드이면 0을 return하고, child가 empty이면 1을 return해준다.
예외처리 해주어야할 부분은 어떤 노드 n의 자식이 1개인데 이 노드가 삭제된 노드인 경우 n도 leaf 노드로 바꿔주어야 한다.

#include <cstdio>
#include <vector>
using namespace std;
int N,root,del;
vector<int> child[50];
int trvs(int n){
    if(n==del) return 0;
    if(child[n].empty()) return 1;
    int ret=0;
    bool f = 0;
    for(auto c : child[n]) {
        if(c==del) f=1;
        else ret+=trvs(c);
    }
    if(f && ret==0) return 1;
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        int par;
        scanf("%d",&par);
        if(par!=-1) child[par].push_back(i);
        else root=i;
    }
    scanf("%d",&del);   
    printf("%d",trvs(root));
} 

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

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

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

[풀이]
배열에 직접 원소를 넣어서 reverse,pop 연산을 하게되면 시간초과가 발생한다.
배열 대신 배열의 왼쪽 index 'l', 오른쪽 index 'r', 현재 뒤집혀 있는지를 체크하는 flag 'rvs' 를 유지하면서
R,D 커맨드마다 위 변수들을 적절히 조절해주면 된다.

주의할 점은 배열에 원소가 모두 삭제되었을 때 배열을 뒤집는 R 연산을 해도 error가 아니라는 점이다.

#include <cstdio>
#include <string>
#include <iostream>
#include <vector>
using namespace std;
int T,N,K;
string cmd,s;
int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie();
    cin >> T;
    while(T--){
        cin >> cmd >> N >> s;
        vector<int> v;
        int prev=1;
        for(int i=1;i<s.size();i++){
            if(i-prev>0){
                if(s[i]==',' || s[i]==']'){
                    string t = s.substr(prev,i-prev);
                    v.push_back(stoi(t));
                    prev=i+1;
                }
            }
        }
        int l=0,r=N-1;
        bool rvs=0,err=0;
        for(auto& c : cmd){
            if(c=='R') rvs = !rvs;
            else{
                if(l>r) {
                    err=1;
                    break;
                }
                if(rvs==0) l++;
                else r--;
            }
        }
        if(err){
            cout << "error" << '\n';
            continue;
        }
        cout << '[';
        if(!rvs) {
            for(int i=l;i<=r;i++){
                cout << v[i];
                if(i!=r) cout << ',';
            }
        }else{
            for(int i=r;i>=l;i--){
                cout << v[i];
                if(i!=l) cout << ',';
            }            
        }
        cout << ']' << '\n';   
    }
} 

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

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

[난이도] Silver1
[유형] 이분탐색

[풀이]
최대 N이 1억으로 너무 크기 때문에 1~N까지 순회하면서 k번째 수를 찾으면 시간초과가 난다.
이분 탐색을 이용해 low : 1 high : N+1 으로 시작해서 k번째 수가 포함된 숫자보다 1 작은 숫자를 범위를 좁혀가며 찾아준다.
그 숫자는 lo가 되게 되고
lo까지 숫자에 포함된 숫자의 개수가 정확히 K개이면 lo의 1의 자리수가 정답이고
K를 초과하면 lo+1(hi)에 K번째 수가 포함되어있으므로 그 수를 찾아준다.

#include <cstdio>
#include <string>
using namespace std;
int N,K;
int check(int m){
    int ret=0;
    int k=1;
    int i=10;
    for(;i<=m;i*=10,k++) ret+=(i-i/10)*k;
    ret+=k*(1+m-i/10);
    return ret;
}
int main(){
    scanf("%d%d",&N,&K);
    int lo=1;
    int hi=N+1;
    int cnt;
    while(lo+1<hi){
        int mid=(lo+hi)/2;
        if(check(mid)<=K) lo=mid;
        else hi=mid;
    }
    cnt = check(lo);
    if(cnt==K) printf("%c",to_string(lo).back());
    else {
        int r = K-cnt;
        string h;
        if(lo==N || to_string(hi).size() < r) {
            puts("-1");
            return 0;
        }
        printf("%c",to_string(hi)[r-1]);
    }
} 

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

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

[난이도] Gold4
[유형] 이분탐색

[풀이]
휴게소가 없는 구간의 최댓값을 기준으로 파라메트릭 서치를 해주면 된다.
매 루프마다 나오는 mid값이 휴게소가 없는 구간의 최댓값이며 이 길이를 이용해
휴게소 사이사이에 지을 수 있는 휴게소를 직접 지어보면서 휴게소를 M개 지을 수 있는 것들이
조건에 부업하는 휴게소가 없는 구간의 길이이다. 이 길이가 최댓값이 나올때까지 서치를 진행하면 된다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,M,L,a[102];
int check(int d){
    int ret=0;
    for(int i=1;i<=N+1;i++){
        int diff = a[i]-a[i-1];
        if(diff>d){
            if(diff%d==0) ret+=diff/d-1;
            else ret+=diff/d;
        }
    }
    return ret;
}
int main(){
    scanf("%d%d%d",&N,&M,&L);
    a[0]=0;
    a[N+1]=L;
    for(int i=1;i<=N;i++) scanf("%d",&a[i]);
    sort(a,a+N+2);
    int l=0;
    int r=L;
    while(l+1<r){
        int mid = (l+r)/2;
        int cnt = check(mid);
        if(M<cnt) l=mid;
        else r=mid;
    }
    printf("%d",r);
} 

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

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

[난이도] Silver3
[유형] DP

[풀이]
DP[i][j] : 가장 마지막에 더한 숫자가 i이며 j를 만들 수 있는 방법의 수.

위와 같이 마지막에 더한 수 i를 기록할 수 있는 2차원 테이블을 만들어서 풀 수 있다.

import java.io.BufferedReader
import java.io.InputStreamReader
val mod = 1e9.toInt()+9
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var t = readLine().toInt()
    val dp = Array<IntArray>(4) { IntArray(100001) }
    dp[1][1]=1
    dp[2][2]=1
    dp[3][3]=1
    for(i in 1..100000){
        for(j in 1..3){
            if(i-j<0) continue
            for(k in 1..3){
                if(j!=k)
                    dp[j][i]=(dp[j][i]+dp[k][i-j])%mod
            }
        }
    }
    while(t-->0){
        val N = readLine().toInt()
        println(((dp[1][N]+dp[2][N])%mod+dp[3][N])%mod)
    }
}

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