프로그래밍

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

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

[풀이]
N 제한이 10밖에 되지 않기 때문에 v[N] 배열에 1부터 N까지 순서대로 저장 한 뒤
순열을 이용해 정답이 될 수 있는 모든 경우의 수를 만들어 보며 조건을 만족하지는지 체크해주면 됩니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,a[11],v[11];
bool check(){
    for(int i=1;i<=N;i++){
        int cnt=0;
        for(int j=1;j<i;j++){
            if(v[j]>v[i]) cnt++;
        }
        if(a[v[i]] != cnt) return 0;
    }
    return 1;
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) {
        scanf("%d",&a[i]);
        v[i]=i;
    }
    do{
    }while(!check() &&next_permutation(v+1,v+1+N));
    for(int i=1;i<=N;i++) printf("%d ",v[i]);
}

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

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

[난이도] Silver2
[유형] 리스트

[풀이]
STL list를 선언한 뒤 iterator를 커서로 취급하여 문제를 해결하면 됩니다.
insert나 erase시 return 되는 iterator의 위치는 헷갈릴 수 있기 때문에 몇가지 예시를 해보면서
iterator의 위치를 파악해야 합니다.

#include <iostream>
#include <list>
#include <string>
using namespace std;
int N;
string s;
int main(){
    cin >> N;
    while(N--){
        cin >> s;
        list<char> li;
        auto it = li.begin();
        for(auto c : s){
            if(c=='-'){
                if(it==li.begin()) continue;
                it--;
                it = li.erase(it);
            }else if(c=='<'){
                if(it==li.begin()) continue;
                it--;
            }else if(c=='>'){
                if(it!=li.end()) it++;
            }else{
                li.insert(it,c);
            }
        }
        for(auto v : li) cout << v;
        cout << "\n";
    }
}

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

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

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

[풀이]
우선순위 큐에 모든 원소들을 넣고 가장 작은 두 수를 뽑아서 계산해서 다시 넣어주고 반복하면 됩니다.

#include <cstdio>
#include <queue>
using namespace std;
int n,m;
using ll = long long;
int main(){
    scanf("%d%d",&n,&m);
    priority_queue<long long> pq;
    while(n--) {
        int v;
        scanf("%d",&v);
        pq.push(-v);
    }
    while(m--){
        ll a = pq.top(); pq.pop();
        ll b = pq.top(); pq.pop();
        pq.push(a+b);
        pq.push(a+b);
    }
    ll ans=0;
    while(!pq.empty()) ans+=pq.top(), pq.pop();
    printf("%lld",-ans);
}

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

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

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

[풀이]
가능한 블루레이 크기의 최솟값은 길이가 가장 짧은 강의의 길이
이고 최댓값은 100000(N의 최댓값) * 10000 (강의 길이의 최댓값) = 10^9
입니다.

범위가 너무 크기 때문에 이분탐색을 이용해서 최솟값을 찾아주면 됩니다.

mid 값을 블루레이의 크기라고 가정 했을 때, bool check(int k) 함수를 이용해서 조건을 만족하는지 체크해주며
범위를 좁혀갈 수 있습니다.

#include <cstdio>
int n,m,a[100000];
bool check(int k){
    int cnt=1,sum=0;
    for(int i=0;i<n;i++){
        if(sum+a[i]>k) {
            sum=0;
            cnt++;
        }
        sum+=a[i];
    }
    return cnt <= m;
}
int main(){
    scanf("%d%d",&n,&m);
    int lo=1,hi=1e9+1;
    for(int i=0;i<n;i++) {
        scanf("%d",&a[i]);
        if(a[i]>lo) lo=a[i];
    }
    lo--;
    while(lo+1<hi){
        int mid=(lo+hi)/2;
        if(check(mid)) hi=mid;
        else lo=mid;
    }
    printf("%d",lo+1);
}

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

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

[난이도] Gold5
[유형] 정렬

[풀이]
각 열 문자로 만든 문자열을 뒤집고 vector에 넣고 정렬해줍니다.
정렬을 해주면 다음과 같은 입력이 주어졌을 때,

mrvica
mrvica
marica
mateja

아래와 같이 정렬이 됩니다.
0:aaaa
1:aarr
2:eiii
3:jccc
4:mmmm

문제의 조건은 결국 위 vector에서 인접한 문자열 두 문자열을 앞에서부터 비교했을 때,
같은 부분이 가장 긴 문자열의 길이를 찾으면 됩니다.

위의 예에서 0번과 1번을 비교했을 때, aa 이므로 이 값을 행의 길이에서 빼주고 1을 빼주면 됩니다.

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int r,c,k,mv;
string s[1000];
int main(){
    cin >> r >> c;
    for(int i=0;i<r;i++) cin >> s[i];
    vector<string> st(c);
    for(int j=0;j<c;j++)
        for(int i=r-1;i>=0;i--) st[j].push_back(s[i][j]);

    sort(st.begin(),st.end());
    for(int i=0;i<c-1;i++){
        int k=0;
        for(int j=0;j<r;j++){
            if(st[i][j]==st[i+1][j]) k++;
            else break;
        }
        mv=max(k,mv);
    }
    cout << r-mv-1;
}

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

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

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

[풀이]
1의 개수끼리 최대 공약수를 구한 뒤,
이 수만큼 1을 출력해주면 정답이라고 합니다.
증명은 못하겠어서 gcd 구하는 연습용으로 풀었습니다..

#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;
ll a,b;
ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    while(b!=0){
        ll c = a%b;
        a=b;
        b=c;
    }
    return a;
}
int main(){
    scanf("%lld%lld",&a,&b);
    for(int i=0;i<gcd(a,b);i++) printf("1");
}

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

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

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

[풀이]
실버1치고 발상이 어려워서 다른 분들의 풀이를 참고했습니다.
(()[[]]) = 2 * (2+3*3) = 2*2 + 2*3*3 이 되는 분배법칙을 이용합니다.
cur 변수를 1로 초기화 해놓고
- 여는 괄호 ( 가 나오면 2를 [가 나오면 3을 곱해줍니다.
- 닫는 괄호가 나오면 해당 괄호가 cur에 미치는 영향은 끝났으므로 2 또는 3으로 나눠줍니다.
  예를 들어, (()[[]]) = 2 * (2+3*3) 에서 두번 째 첫 번째 ) 가 나왔을 때, cur은 2*2에서 2*2/2 가 되어 다시 2가 됩니다.
  그래야, 3*3에 2만 곱해줄 수 있기 때문입니다.
- () 혹은 [] 모양의 인접한 올바른 문자열이라면 2*2 + 2*3*3 에서 한 덩어리의 값이 끝남을 의미하므로 나누기 전에 cur의 값을 total에 더해 줍니다.
- 중간중간 올바른 문자열이 아닌 경우를 체크하여 0을 return 해줍니다.
- 모든 문자열을 순회하고도 stack에 값이 남아있다면 올바른 문자열이 아니므로 0을 return 해줍니다.

#include <cstdio>
#include <stack>
#include <string>
#include <iostream>
using namespace std;
string s;
int sol(){
    stack<char> st;
    int total=0,cur=1;
    for(int i=0;i<s.size();i++){
        if(s[i]=='('){
            cur*=2;
            st.push(s[i]);
        }else if(s[i]=='['){
            cur*=3;
            st.push(s[i]);
        }else{
            if(st.empty()) return 0;
            if(s[i]==')') {
                if(st.top()!='(') return 0;
            }else{
                if(st.top()!='[') return 0;
            }
            st.pop();
            if(s[i-1]=='('||s[i-1]=='[') total+=cur;
            if(s[i]==')') {
                cur/=2;
            }else{
                cur/=3;
            }
        }
    }
    if(!st.empty()) return 0;
    return total;
}
int main(){
    cin >> s;
    cout << sol();
}

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

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

[난이도] Silver1
[유형] DFS

[풀이]
dfs 기본문제 입니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,a[501][501],dy[4]={-1,1,0,0},dx[4]={0,0,1,-1},cnt,ans;
int dfs(int y,int x){
    a[y][x]=2;
    int ret=1;
    for(int i=0;i<4;i++){
        int ny=y+dy[i], nx=x+dx[i];
        if(ny<0||nx<0||ny>=n||nx>=m||a[ny][nx]!=1) continue;
        ret+=dfs(ny,nx);
    }
    return ret;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++) scanf("%d",&a[i][j]);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i][j]==1){
                cnt++;
                ans = max(ans,dfs(i,j));
            }
        }
    }
    printf("%d\n%d",cnt,ans);
}

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