프로그래밍

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

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

[풀이]
문제의 조건대로 구현해주면 됩니다.

#include <cstdio>
int a[5];
void prt(){
    for(int i=0;i<5;i++) printf("%d ",a[i]);
    puts("");
}
bool cmp(int i,int j){
    if(a[i]>a[j]){
        int tmp=a[i];
        a[i]=a[j];
        a[j]=tmp;
        return true;
    }
    return false;
}
int main(){
    for(int i=0;i<5;i++) scanf("%d",&a[i]);
    while(1){
        bool ok=0;
        for(int i=0;i<4;i++){
            if(cmp(i,i+1)) {
                ok=1;
                prt();
            }
        }
        if(!ok) break;
    }
}

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

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

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

[풀이]
어떤 행 i,j가 K번 스위치를 눌렀을 때 두 행 모두 켜져있는 상태가 되려면
i,j 행은 초기 상태가 같아야 합니다.
왜냐하면 어떤 열 m의 초기 상태가 달라 lamp[i][m] != lamp[j][m] 상태인 경우
m번 열의 스위치를 아무리 눌러도 lamp[i][m]과 lamp[j][m] 는 동시에 바뀌기 때문에
계속 lamp[i][m] != lamp[j][m] 상태일 수밖에 없습니다.

그러므로 K번 스위치를 눌러서 켜진 상태(모든 열이 1인 상태)를 만들 수 있는
행 i에 대해서 i행과 같은 초기상태를 가지는 행 j의 개수를 구해주면 됩니다.
이 값을 모든 i에 대해 구해주면서 최댓값을 업데이트 해주면서 나온 최종 값이 정답이 됩니다.

K번 스위치를 눌러서 켜진 상태를 만들 수 있는지는
0의 개수가 K보다 작으면서, 0의 개수를 2로 나눈 나머지와 K를 2로 나눈 나머지가 같아야 합니다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int N,M,K,ans;
string lamp[50];
int main(){
    cin >> N >> M;
    for(int i=0;i<N;i++) cin >> lamp[i];
    cin >> K;
    for(int i=0;i<N;i++){
        auto s = lamp[i];
        int cnt=0;
        for(int j=0;j<M;j++) if(s[j]=='0') cnt++;
        if(cnt > K || cnt%2 != K%2) continue;
        int sameCnt=0;
        for(int j=0;j<N;j++) if(s==lamp[j]) sameCnt++; 
        ans=max(ans,sameCnt);
    }
    printf("%d",ans);
}

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

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

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

[풀이]
오븐의 지름이 넓을 수록 피자를 넣기에 유리하지만 오븐 아래층의 지름이 아무리 넓어도
윗 층의 지름이 더 좁다면 윗 층 지름중 가장 좁은 지름만큼의 넓이를 가진 피자밖에 담을 수가 없습니다.
이를 이용해 O(N) 시간에 문제를 해결할 수 있습니다.

a 배열을 선언하여 다음과 같이 정의합니다.
a[i] : 1~i 층까지의 지름 중 가장 좁은 지름

점화식은 다음과 같습니다. 일종의 메모제이션입니다.
a[i] = min(i번 층의 지름,a[i-1])

이런 식으로 저장하게 되면 a 배열은 내림차순 형태를 띄게 됩니다.

이제 피자를 순서로 입력받으면서
D층부터 넣을 수 있는 곳에 차례대로 채워가면 됩니다.
모든 피자를 넣을 수 없는 경우 0을 출력해야 하는 것을 주의해야 합니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int D,N,a[300001];
int main(){
    scanf("%d%d",&D,&N);
    for(int i=0;i<=D;i++) a[i]=2e9;
    for(int i=1;i<=D;i++) {
        int v;
        scanf("%d",&v);
        a[i] = min(v,a[i-1]);
    }
    int cur=D, ans=0;
    while(N--){
        int v;
        scanf("%d",&v);
        for(;cur>=0;cur--){
            if(v<=a[cur]){
                ans=cur;
                cur--;
                break;
            }    
        }
    }
    printf("%d",ans);
}

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

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

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

[풀이]
결과 문자열 T의 뒤부터 확인하면서, A가 있으면 첫번째 규칙,
B가 있으면 두번째 규칙을 거꾸로 적용해주면서
T가 S가 되는 순간이 있으면 1을 아니면 0을 출력해주면 됩니다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string A,B;
int main(){
    cin >> A >> B;

    while(!B.empty()){
        if(A==B) {
            cout << "1";
            return 0;
        }
        if(B.back()=='A') B.pop_back();
        else {
            B.pop_back();
            reverse(B.begin(),B.end());
        }
    }
    cout << "0";
}

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

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=408&sw_prbl_sbms_sn=16793

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

[풀이]
int형 배열에 저장해서 비교하려면 다소 귀찮기 때문에
string에 입력값을 저장한 뒤 "12345678"이면 ascending, "87654321"이면 descending, 둘다 아니라면 mixed를 출력해주면 됩니다.

#include <string>
#include <iostream>
using namespace std;
string s(8,' ');
int main(){
    for(int i=0;i<8;i++) cin >> s[i];
    if(s=="12345678") cout << "ascending";
    else if(s=="87654321") cout << "descending";
    else cout << "mixed";
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level2/8단_변속기.cpp

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=407&sw_prbl_sbms_sn=16789

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

[풀이]
N번 P를 곱할때마다 모듈러 연산을 해주면 됩니다.
계산중 int 범위를 넘어갈 수 있으므로 처음부터 long long으로 자료형을 잡고 하면 편합니다.

#include <cstdio>
using ll = long long;
int N;
ll K,P,mod=1000000007;
int main(){
    scanf("%lld%lld%d",&K,&P,&N);
    while(N--) K=(K*P)%mod;
    printf("%lld",K);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level2/바이러스.cpp

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=584

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

[풀이]
0~99 번째 구간의 제한속도와 실제 운행한 속도를 vector에 저장한 뒤 그 차의 최댓값을 구해주면 됩니다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,M,u,v,ans;
int main(){
    scanf("%d%d",&N,&M);
    vector<int> a,b;
    while(N--){
        scanf("%d%d",&u,&v);
        while(u--) a.push_back(v);
    }
    while(M--){
        scanf("%d%d",&u,&v);
        while(u--) b.push_back(v);        
    }
    for(int i=0;i<100;i++) ans=max(ans,b[i]-a[i]);
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level2/GBC.cpp

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

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

[풀이]
N제한이 200으로 여유롭기 때문에 효율적인 알고리즘 보다는 구현능력을 묻는 문제입니다.

아래 코드에서는 map<int,vector<pair<int,int>>> 타입의 block,empt(y) map을 선언하여
block에는 key색상 블록 4개의 좌표를, empty에는 key색상 블록이 직사각형이 되기 위해 채워줘야 하는 좌표 2개를 저장하기로 하였습니다.

block을 구하는 것은 board를 한번 순회하면서 block[board[y][x]].push_back({y,x})와 같이 간단하게 구할 수 있지만,
empty를 구하는 방법은 여러가지가 있을 수 있는데 시간 제한이 여유롭기 때문에 가장 단순한 방법으로 구하였습니다.

각 종류의 블록마다 board를 (0,0) ~ (N-1,N-1) 까지 순회하면서 2x3,3x2 모양을 모든 점에서 확인하는 방식입니다.
예를들어 숫자가 K인 블록의 empty를 찾고 싶을 때, 2x3, 3x2 모양의 모든 직사각형을 확인하면서 K가 적혀있는 점이 4개 있는 곳의 나머지 2개의 점이 K의 empty 블록들입니다.

empty를 구하였다면 while문을 돌면서 지울 수 있는 블록들을 더이상 지울 수 없을때까지 지워주면 됩니다.
empty인 블록 2개 모두 다른 블록의 방해를 받지 않고 보드의 가장 위인 (-1,x)에 도달하면 해당 종류의 블록은 지울 수 있는 것입니다.

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cstdio>
using namespace std;
int dy1[6]={0,0,0,1,1,1};
int dx1[6]={0,1,2,0,1,2};
int dy2[6]={0,1,2,0,1,2};
int dx2[6]={0,0,0,1,1,1};
int N;
map<int,vector<pair<int,int>>> block,empt;
vector<vector<int>> board;
bool check(int c,vector<pair<int,int>> v){
    for(auto [y,x] : v){
        while(y>=0){
            if(board[y--][x]!=0) return 0;
        }
    }
    for(auto [y,x] : block[c]) board[y][x]=0;
    return 1;
}
int solution(vector<vector<int>> _board) {
    int answer = 0;
    board=_board;
    N=board.size();
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++) 
            if(board[i][j]>0) block[board[i][j]].push_back({i,j});

    for(auto [v,mp] : block){
        for(int i=0;i<N-1;i++){
            for(int j=0;j<N-2;j++){
                vector<pair<int,int>> tmp;
                int cnt=0;
                for(int d=0;d<6;d++){
                    int ny=i+dy1[d];
                    int nx=j+dx1[d];
                    if(board[ny][nx]==v) cnt++;
                    else tmp.push_back({ny,nx});
                }
                if(cnt==4) empt[v]=tmp;
            }
        }
    }
    for(auto [v,mp] : block){
        for(int i=0;i<N-2;i++){
            for(int j=0;j<N-1;j++){
                vector<pair<int,int>> tmp;
                int cnt=0;
                for(int d=0;d<6;d++){
                    int ny=i+dy2[d];
                    int nx=j+dx2[d];
                    if(board[ny][nx]!=v) tmp.push_back({ny,nx});
                    else cnt++;
                }
                if(cnt==4) empt[v]=tmp;
            }
        }
    }
    bool ok=1;
    vector<bool> erased(201,0);
    while(ok){
        ok=0;
        for(auto [c,v] : empt){
            if(erased[c]) continue;
            if(check(c,v)){
                erased[c]=1;
                ok=1;    
                answer++;
            }
        }
    }
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/블록게임.cpp