프로그래밍

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

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

[풀이]
1~N까지의 수를 string으로 변환한 뒤 3,6,9의 개수를 찾아서 더해주면 됩니다.

#include <cstdio>
#include <string>
using namespace std;
int N,ans;
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        string s = to_string(i);
        for(auto c : s) {
            if(c=='3' || c=='6'||c=='9') ans++;
        }
    }
    printf("%d",ans);
}

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

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

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

[풀이]
struct P{
    int id,t,pos;
}
id : id, t : 계산이 끝나는 시간, pos :계산대의 위치
위와 같이 구조체를 정의해줍니다. 그리고
우선순위큐의 comparator 객체를 정의하여
끝나는 시간 t가 작을수록 , 출구에 가까운 계산대 (pos가 클수록)
top에 오도록 해줍니다.

그 뒤 매 루프마다 끝나는 시간이 빠른 모든 원소들을 pop 해준 뒤
ans vector에는 id를 저장해줍니다. 출구쪽부터 pop되기 때문에 이 순서로 ans vector에 저장해주면 됩니다.

rp vector에는 pop되는 순서대로 pos를 저장해줍니다. 이 rp vector를 뒤집은 뒤 반대로 순회하면서
나온 pos에 순차적으로 고객들을 push해줍니다. 시간은 현재 pop된 t+(고객의 물건 수)를 해주면
끝나는 시간을 넣어줄 수 있습니다.

위 과정을 반복하면서 ans vector를 채워주면 정답을 구할 수 있습니다.

#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
int N,k;
pair<int,int> a[1000000];
struct P{
    int id,t,pos;
}; 
struct cmp{
    bool operator()(P& a,P& b){
        if(a.t > b.t) return true;
        else if(a.t == b.t){
            if(a.pos<b.pos) return true;
        }
        return false;
    }
};
int main(){
    scanf("%d%d",&N,&k);
    for(int i=0;i<N;i++) scanf("%d%d",&a[i].first,&a[i].second);
    priority_queue<P,vector<P>,cmp> pq;
    int i=0;
    for(;i<N&&i<k;i++) pq.push({a[i].first,a[i].second,i});
    vector<int> ans;
    for(;i<N;i++){
        auto [id,t,pos] = pq.top();
        vector<int> rp;
        while(!pq.empty() && pq.top().t==t){
            rp.push_back(pq.top().pos);
            ans.push_back(pq.top().id);
            pq.pop();
        }
        reverse(rp.begin(),rp.end());
        for(auto r : rp){
            pq.push({a[i].first,t+a[i].second,r});
            i++;
            if(i>=N) break;
        }
        i--;
    }
    while(!pq.empty()){
        auto [id,t,pos] = pq.top(); pq.pop();
        ans.push_back(id);
    }
    long long total=0;
    for(int i=1;i<=N;i++) total+=i*(long long)ans[i-1];
    printf("%lld",total); 
}

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

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

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

[풀이]
가로 선분들과 세로 선분들을 나눠서 생각해보면
결국 가로 선분이 최대 몇개 겹칠 수 있는지, 세로 선분이 최대 몇개 겹칠 수 있는지를 각각 구해서
둘중 최댓값을 정답으로 출력하는 문제입니다.
번갈아 가면서 입력되는 가로 선분과 세로 선분을 각각 vector에 저장해줍니다.
a[i%2].push_back({l,1});
a[i%2].push_back({r,-1});
위와 같이 이런 스위핑 문제를 풀때 자주 사용하는 누적합 개념을 이용합니다.
선분이 시작되는 점에서 1을 더해주고 선분이 끝나는 점에서 1을 빼주면 어느 점에서 최대로 겹치는지
확인이 가능합니다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n,ans;
pair<int,int> p[100000];
vector<pair<int,int>> a[2];
int main(){ 
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d",&p[i].first,&p[i].second);
    for(int i=1;i<=n;i++){
        int l,r,q=i,z=i-1;
        if(q==n) q=n-1,z=0;
        if(p[q].first==p[z].first) {
            l=min(p[q].second,p[z].second);
            r=max(p[q].second,p[z].second);
        }else{
            l=min(p[q].first,p[z].first);
            r=max(p[q].first,p[z].first);            
        }
        a[i%2].push_back({l,1});
        a[i%2].push_back({r,-1});
    }
    for(int i=0;i<2;i++){
        sort(a[i].begin(),a[i].end());
        int tmp=0;
        for(auto [t,v] : a[i]){
            tmp+=v;
            ans=max(tmp,ans);
        }
    }
    printf("%d",ans);
}

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

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

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

[풀이]
추의 무게를 더하거나 빼서 만들 수 있는 모든 무게를 구해주면
이 무게들이 추를 이용해 만들 수 있는 무게들입니다.

#include <cstdio>
int k,v[14],a[3000000],sum,ans;
void sol(int n,int cur){
    if(cur>=1) {
        if(!a[cur]) ans++;
        a[cur]=1;
    }
    if(n==k) return;
    sol(n+1,cur+v[n]);
    sol(n+1,cur-v[n]);
    sol(n+1,cur);
}
int main(){
    scanf("%d",&k);
    for(int i=0;i<k;i++){
        scanf("%d",&v[i]);
        sum+=v[i];
    }
    sol(0,0);
    printf("%d",sum-ans);
}

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

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

[난이도] Silver1
[유형] 재귀

[풀이]
sol(int l,int r,bool use)
l : 좌측 index,
r :오른쪽 index,
use : 문자 1개를 제거하는 연산을 사용할 수 있는 상태인지

위의 재귀함수를 만들어서,
s[l]!=s[r]인 상태가 왔을 때, 제거하는 연산 (use)를 사용해준 뒤 재귀호출을 한번 더 해준 뒤
그 결과를 출력해주면 됩니다.

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
string s;
int tc;
int sol(int l,int r,bool use){
    while(l<=r){
        if(s[l]==s[r]) {
            l++,r--;
            continue;
        }
        if(!use) return 2;
        int ret=2;
        if(s[l+1]==s[r]) {
            ret=sol(l+1,r,0);
            if(ret!=2) return 1;
        }
        if(s[l]==s[r-1]) {
            ret=sol(l,r-1,0); 
            if(ret!=2) return 1;
        }
        return ret;
    }
    return 0;
}
int main(){
    cin >> tc;
    while(tc--){
        cin >> s;
        printf("%d\n",sol(0,s.size()-1,1));
    } 
}

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

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

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

[풀이]
우측에서 바라봤을 때 현재 보이는 막대기의 높이만 cur 저장해주면서
다음 막대가 cur보다 높으면 cur을 이 막대의 높이로 업데이트 하고 정답에 1을 더해줍니다.
만약 cur보다 작으면 보이지 않는 막대이므로 무시해줍니다.

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

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

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

[난이도] Gold3
[유형] 비트마스킹

[풀이]
모든 주민의 이름을 서로 XOR 계산을 하게 되면 O(N^2)의 시간복잡도로 시간초과가 발생하게 됩니다.

잘 생각해보면 각 XOR 계산의 결과가 얼마인지는 알 필요가 없고 총 합만 구하면 되기 때문에,
각 자리수끼리의 XOR 연산에서 총 얼마의 친밀도가 발생하는지 계산해서 답에 더해주면 됩니다.
예를 들어,

1001
0110
1000

위와 같이 세가지 수가 있을 때, 제일 좌측 4번째 자릿수의 값은 각각
1
0
1

입니다. 여기서 1이 2개, 0이 1개이기 때문에 서로간의 XOR 연산에서
2x1=2 가 생김을 알 수 있습니다.
이 숫자에 자릿수 2^3을 곱해주면 2 x (2^3) 이 되는데 이 값을 답에 더해주면 4번째 자릿수에서
발생하는 숫자의 계산은 끝이 납니다.

이렇게 모든 자릿수에 대해서 위와 같이 1과 0이 몇개 있는지를 체크해서 답에 더해주면 됩니다.

#include <cstdio>
int N;
long long onecnt[20];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        int v;
        scanf("%d",&v);
        int j=0;
        while(1){
            if(v/2==0) {
                onecnt[j]++;
                break;
            }
            onecnt[j++]+=v%2;
            v/=2;
        }
    }
    long long ans=0;
    for(int i=0;i<20;i++) ans+=(1<<i)*(N-onecnt[i])*onecnt[i];
    printf("%lld",ans);
}

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

https://programmers.co.kr/learn/courses/30/lessons/92345

[난이도] level3
[유형] Min Max 게임

[풀이]
공식 풀이 :https://programmers.co.kr/learn/courses/30/lessons/92345

#include <string>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
int dy[4]={-1,1,0,0},N,M;
int dx[4]={0,0,1,-1};
pair<int,int> sol(int y,int x,int ty,int tx,vector<vector<int>> board){
    if(!board[y][x]) return {0,0};
    int minv=1e9,maxv=-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||!board[ny][nx]) continue;
        auto b = board;
        b[y][x]=0; 
        auto [w,c] = sol(ty,tx,ny,nx,b);
        if(w) maxv = max(maxv,c);
        else minv = min(minv,c);
    }
    if(minv!=1e9) return {1,minv+1};
    if(maxv!=-1) return {0,maxv+1};
    return {0,0};
}
int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
    N=board.size();
    M=board[0].size();
    return sol(aloc[0],aloc[1],bloc[0],bloc[1],board).second;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/사라지는_발판.cpp