프로그래밍

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

[난이도] Silver3
[유형] 스택

[풀이]
1~n 순서로 무조건 push해야 하므로 for문을 돌면서 일단 push해주고
만약 top이 현재 나와야 하는 수열 값이라면 while문을 돌면서 pop을 해준다.
만약 위 과정을 마치고 스택이 비어있지 않다면 수열을 만들 수 없는 경우이다.

복잡하게 조건을 생각하면서 풀려고 하면 어렵기 때문에 스택의 empty 유무로 판단해야 한다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.collections.ArrayList

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var n = readLine().toInt()
    val st = Stack<Int>()
    val arr = IntArray(n)
    for(i in 0..n-1) arr[i]=readLine().toInt()
    var idx=0;
    var ans=ArrayList<Char>()
    for(i in 1..n){
        st.push(i)
        ans.add('+')
        while(!st.empty() && st.peek()==arr[idx]){
            st.pop()
            ans.add('-')
            idx++
        }
    }
    if(!st.empty()) println("NO")
    else for(c in ans) println(c)
}

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

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

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

[풀이]
reversed 함수를 이용해 뒤집기

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var n = readLine().toInt()
    while(n-->0){
        var sp = readLine().split(" ");
        for(a in sp){
            print(a.reversed()+' ')
        }
        println()
    }
}

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

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

[난이도] Silver4
[유형] 스택

[풀이]
코틀린으로 문제를 풀때 입력은 BufferedReader(InputStreamReader(System.`in`)) 으로 받는 것이 좋다.
Scanner로 받으니까 시간초과가 났다

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
    var n = readLine().toInt()
    var s = Stack<Int>()
    while(n-->0){
        var rd = readLine().split(" ")

        val ret = when(rd[0]){
            "push" -> {
                var v = rd[1].toInt()
                s.push(v)
                null
            }
            "pop" -> {
                if(!s.empty()) s.pop()
                else -1
            }
            "top" -> {
                if(!s.empty()) s.peek()
                else -1
            }
            "size" -> s.size
            else -> {
                if(s.empty()) 1
                else 0
            }
        }
        ret?.let{println(ret)}
    }
}

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

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

[난이도] Gold3
[유형] 스위핑

[풀이]
일단 좌측 x값을 기준으로 정렬을 한다.
y와 관계없이 (xi1,xi2) (xj1,xj2)가 이동 가능한 점이려면
x12>=xj1 를 만족하면 된다.
즉, y와 상관없이 연속된 직선상에 포함되는 점들은 이동이 가능한 점(집합)이다.

스위핑을 해주면서 어떤 그룹에 속하는지 배열에 저장하면 답을 찾을 수 있다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
int N,Q;
struct P{
    int x1,x2,num;
};
bool cmp(P a,P b){
    return a.x1 < b.x1;
}
P tree[100001];
int g[100001];
int main(){
    scanf("%d%d",&N,&Q);
    for(int i=0;i<N;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        tree[i]={a,b,i};
    }
    sort(tree,tree+N,cmp);

    int sid=0,e=tree[0].x2;
    g[0]=sid;

    for(int i=1;i<N;i++){
        if(tree[i].x1<=e){
            if(tree[i].x2>e) e=tree[i].x2;    
        }else{
            sid++;
            e=tree[i].x2;
        }
        g[tree[i].num]=sid;
    }
    while(Q--){
        int u,v;
        scanf("%d%d",&u,&v);
        u--,v--;
        if(g[u]==g[v]) puts("1");
        else puts("0");
    }
}

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

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

[난이도] Gold3
[유형] 자료구조

[풀이]
GOOD인 수는 set에 저장한다.
2중으로 모든 pair를 확인하면서 set에 만들 수 있는 수를 저장한다.
이때 주의할 것이
a[i]=0, a[j]=3 이런 경우에 set에 3을 그냥 넣으면 안된다.
왜냐하면 0+3으로 3은 자기 자신을 포함해서 만들어진 수이므로 GOOD인 수가 아니다.
이 경우를 제외하기 위해 일단 a[i] 또는 a[j]가 0인 경우는 제외하고 set에 저장해준다.

0과 관련하여 나올 수 있는 예외를 생각해보면 다음과 같다.

case 1) 0+3과 같이 자기 자신을 포함했지만 3이 GOOD인 수이려면 수열에 3이 2개 이상 있으면 된다. (ex 0,3,3)
case 2) 0이 GOOD인 수이려면 (-3)+3 이런 식의 수가 존재하여 위의 루프에서 set에 추가되거나, 0끼리의 합으로 GOOD인 수를 만들어야 한다. 이때, 0이 2개만 있게 되면 자기 자신을 포함하여 0을 만든 것이기 때문에 GOOD인 수가 될 수 없고,
0이 3개 이상 있어야 한다.

위의 예외 처리를 위해서 map을 이용해 a 배열의 각 원소가 개수가 몇개씩 있는지를 counting해서 저장해주었다.
case 1을 처리하기 위해 => map[0]이 3 이상이면 0을 set에 넣어주고.
case 2를 처리하기 위해 => map[0]이 1 이상이고, 현재 확인중인 원소 A가 2개 이상이면 A를 set에 넣어준다.

이제 set에는 GOOD인 수가 모두 저장되게 되었으므로 답을 출력해주면 된다.

#include <cstdio>
#include <map>
#include <set>
using namespace std;
int N,a[2000];
map<int,int> cnt;
int main(){

    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    set<int> s;
    for(int i=0;i<N-1;i++){
        cnt[a[i]]++;
        for(int j=i+1;j<N;j++) {
            if(a[i]!=0&&a[j]!=0) s.insert(a[i]+a[j]);
        }
    }
    cnt[a[N-1]]++;
    for(auto v : cnt){
        if(v.first==0) {
            if(v.second>2) s.insert(0);
        }else{
            if(cnt.find(0)!=cnt.end() && v.second>1) s.insert(v.first);
        }
    }

    int ans=0;
    for(int i=0;i<N;i++) {
        if(s.find(a[i]) !=s.end()) {
            ans++;
        }
    }
    printf("%d",ans);
}

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

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

[난이도] Gold3
[유형] DP

[풀이]
dp[i] : 1~i번 기지국까지 설치 했을 때의 최소 설치 비용.

dp[i]를 구하기 위해서는 i를 어느 박스에 포함시킬지를 정해야한다.
만약 어떤 j~i를 이은 박스에 포함시키려면 j~i 박스의 최솟값 + dp[j-1] (j-1번까지 설치했을 때의 최솟값)을 더해주면 된다.

점화식
dp[i]= min(dp[i],dp[j-1]+max(2*mH,a[i].first-a[j].first)); (j : 1~i, mH : 1~i까지 높이의 최댓값, a.first : x좌표)

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int N,dp[10001],inf=9e8;
pair<int,int> a[10001];
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d%d",&a[i].first,&a[i].second);
    sort(a+1,a+N+1);
    for(int i=1;i<=N;i++){
        int mH=0;
        dp[i]=inf;  
        for(int j=i;j>=1;j--){
            mH=max(mH,abs(a[j].second));
            dp[i]=min(dp[i],dp[j-1]+max(2*mH,a[i].first-a[j].first)); 
        }
    }
    printf("%d",dp[N]);
}

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

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

[난이도] Gold5
[유형] DP

[풀이]
DP[n][m] : 자리수가 n이면서 m으로 시작하는 수의 개수

#include <cstdio>
int t,N;
long long a[65][10];
int main(){
    scanf("%d",&t);
    for(int i=0;i<10;i++) a[1][i]=1;
    for(int i=2;i<65;i++)
        for(int j=0;j<10;j++)
            for(int k=0;k<=j;k++) 
                a[i][j]+=a[i-1][k];
    while(t--){
        scanf("%d",&N);
        long long ans=0;
        for(int i=0;i<10;i++) ans+=a[N][i];
        printf("%lld\n",ans);
    }
}

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

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

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

[풀이]
N자리에서 K자리를 지워야 하므로
N-K 자리의 수를 만들어야 한다.
가장 큰 자리수에 큰 수가 올수록 유리하다.
큰 자리수의 숫자부터 b[0]~b[N-1]에 저장하기로 하면
b[0]은 a[0]~a[N-K] 중에 가장 큰수,
b[1]은 (b[0]의 a에서의 index)~a[N-K+1] 중에 가장 큰수,
b[2]은 (b[1]의 a에서의 index)~a[N-K+2] 중에 가장 큰수
....
으로 구할 수 있다.
그런데 for문으로 큰 수들을 구하면 시간초과가 나므로 우선순위 큐를 이용하였다.

a 배열에서 0~N-K-1 까지의 수를 pq에 {a[i],i} pair로 index까지 같이 넣어놓고
K번의 반복동안
N-K+i번 pair를 추가하면서 pq에서 최댓값을 찾으면 NlogN의 시간으로 답을 찾을 수 있다.

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int N,a[500000],K;

struct cmp{
    bool operator()(pair<int,int> a,pair<int,int> b){
        if(a.first<b.first) return 1;
        else if(a.first==b.first) return a.second > b.second;
        return 0;
    }
};
int main(){
    scanf("%d%d",&N,&K);
    for(int i=0;i<N;i++) scanf("%1d",&a[i]);
    priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> pq;
    K=N-K;
    for(int i=0;i<N-K;i++) pq.push({a[i],i});
    int s=-1,e;
    for(int i=0;i<K;i++){
        e=N-K+i;
        pq.push({a[e],e});
        while(!pq.empty()){
            auto qt = pq.top(); pq.pop();
            if(qt.second>s) {
                s=qt.second;
                break;
            }
        }
        printf("%d",a[s]);
    }
}

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