백준 BOJ 구현, 시뮬레이션 문제 위주 풀이 모음 220811

백준 BOJ 12100번 : 2048 (Easy)

문제 난이도 : Gold II

알고리즘 분류 : 구현

 

 

 

게임 2048을 구현하여, N x N 격자의 보드가 주어질 때 최대 5번 이동시켜서 얻을 수 있는 최대 숫자의 크기를 구하는 문제이다. (코딩하다가 심심해서 잠깐 해봤다.)

 

내가 꽤 오래 미루던 구현 문제이다.

구현 문제는 심지어 풀이를 참고해도 내가 다시 짜려면 한참 걸린다.

아무튼 이 문제는 구조 자체는 단순 DFS 방식으로 짤 수 있는데, 문제는 네 방향으로 숫자가 이동하는 것을 구현하기가 귀찮다.

 

구현 방법은 이러한데, 예를 들어 모든 숫자를 밑으로 이동시켰을 때 밑에서 1번째 칸에서 맨 밑으로 검사, 밑에서 2번째 칸에서 맨 밑까지 검사, 밑에서 3번째 칸에서 맨 밑까지 검사, ...의 방식으로 맨 위까지 누적해서 확인해주면 된다. (N이 20 이하라 각 이동마다 3중 반복문을 두어도 쉽게 돌아간다.)

이 때 문제점은 한 번 합쳐진 숫자는 해당 이동에서 더 이상 합쳐지면 안되는데, 이것은 2차원 bool 벡터 등을 활용하여 이미 합쳐진 숫자임을 체크해줄 수 있다.

 

위로 이동시키는 함수는 왼쪽으로 이동시키는 함수와 [i][j]값만 [j][i]값으로 바꿔주면 되고, 아래로 이동시키는 함수도 오른쪽으로 이동시키는 함수와 같은 관계임을 생각해보면 함수 2개만 제대로 구현해준다면 나머지는 금방 작성이 가능할 것이다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

int N, ans = 0;

vector<vector<int>> u(vector<vector<int>> v) {
    vector<vector<bool>> b(N, vector<bool>(N));

    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            for(int k=j-1; k>=0; k--) {
                if(v[k][i] == 0) {
                    v[k][i] = v[k+1][i];
                    v[k+1][i] = 0;
                }
                else if(v[k][i] == v[k+1][i] && !b[k][i]) {
                    v[k][i] *= 2;
                    v[k+1][i] = 0;
                    b[k][i] = true;

                    break;
                }
                else break;
            }

    return v;
}

vector<vector<int>> d(vector<vector<int>> v) {
    vector<vector<bool>> b(N, vector<bool>(N));

    for(int i=0; i<N; i++)
        for(int j=N-1; j>=0; j--)
            for(int k=j; k<N-1; k++) {
                if(v[k+1][i] == 0) {
                    v[k+1][i] = v[k][i];
                    v[k][i] = 0;
                }
                else if(v[k+1][i] == v[k][i] && !b[k+1][i]) {
                    v[k+1][i] *= 2;
                    v[k][i] = 0;
                    b[k+1][i] = true;

                    break;
                }
                else break;
            }

    return v;
}

vector<vector<int>> l(vector<vector<int>> v) {
    vector<vector<bool>> b(N, vector<bool>(N));

    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            for(int k=j-1; k>=0; k--) {
                if(v[i][k] == 0) {
                    v[i][k] = v[i][k+1];
                    v[i][k+1] = 0;
                }
                else if(v[i][k] == v[i][k+1] && !b[i][k]) {
                    v[i][k] *= 2;
                    v[i][k+1] = 0;
                    b[i][k] = true;

                    break;
                }
                else break;
            }

    return v;
}

vector<vector<int>> r(vector<vector<int>> v) {
    vector<vector<bool>> b(N, vector<bool>(N));

    for(int i=0; i<N; i++)
        for(int j=N-1; j>=0; j--)
            for(int k=j; k<N-1; k++) {
                if(v[i][k+1] == 0) {
                    v[i][k+1] = v[i][k];
                    v[i][k] = 0;
                }
                else if(v[i][k+1] == v[i][k] && !b[i][k+1]) {
                    v[i][k+1] *= 2;
                    v[i][k] = 0;
                    b[i][k+1] = true;

                    break;
                }
                else break;
            }

    return v;
}

void f(vector<vector<int>> v, int cnt) {
    if(cnt == 5) {
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++) ans = max(ans, v[i][j]);

        return;
    }

    f(u(v), cnt+1);
    f(d(v), cnt+1);
    f(l(v), cnt+1);
    f(r(v), cnt+1);
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cin >> N;

    vector<vector<int>> v(N, vector<int>(N));

    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++) cin >> v[i][j];

    f(v, 0);

    cout << ans << "\n";
}

 

 

백준 BOJ 3932번 : Unreliable Messengers

문제 난이도 : Silver III

알고리즘 분류 : 문자열, 구현

 

명령어가 주어지고 암호문이 주어질 때 원래 문자열을 구하는 문제이다.

J는 문자를 왼쪽으로 한 자리씩 이동하고, C는 문자를 오른쪽으로 한 자리씩 이동하고, E는 문자열 왼쪽 절반과 오른쪽 절반을 바꾸고, A는 문자열을 뒤집고, P는 모든 숫자를 1씩 증가시키고, M은 모든 숫자를 1씩 감소시킨다.

 

모든 명령어에 대해 거꾸로 수행하면서, 반대로 해주면 된다.

예를 들어 J의 경우 문자를 왼쪽으로 이동했으므로 오른쪽으로 한 칸씩 이동해주면 명령어 수행 전의 문자열이 될 것이다.

순수 구현량이 많으므로 실수에 주의하자.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;

    while(T--) {
        string com, str; cin >> com >> str;

        for(int i=com.length()-1; i>=0; i--) {
            if(com[i] == 'J') str = str.back() + str.substr(0, str.length()-1);
            else if(com[i] == 'C') str = str.substr(1, str.length()-1) + str.front();
            else if(com[i] == 'E') {
                if(str.length() % 2 == 0) str = str.substr((str.length()+1)/2, str.length()/2) + str.substr(0, str.length()/2);
                else str = str.substr((str.length()+1)/2, str.length()/2) + str[str.length()/2] + str.substr(0, str.length()/2);
            }
            else if(com[i] == 'A') reverse(str.begin(), str.end());
            else if(com[i] == 'P') {
                for(int j=0; j<str.length(); j++) {
                    if(str[j] == '0') str[j] = '9';
                    else if(str[j] >= '1' && str[j] <= '9') str[j]--;
                }
            }
            else if(com[i] == 'M') {
                for(int j=0; j<str.length(); j++) {
                    if(str[j] == '9') str[j] = '0';
                    else if(str[j] >= '0' && str[j] <= '8') str[j]++;
                }
            }
        }

        cout << str << "\n";
    }
}

 

 

백준 BOJ 5397번 : 키로거

문제 난이도 : Silver II

알고리즘 분류 : 스택

 

커서를 이동시키며 문자열을 작성할 때, 커서의 좌우 이동과 백스페이스를 포함한 입력 키 순서가 주어진다면 최종적으로 작성되는 문자열이 무엇인지 구하는 문제이다.

 

스택 2개를 이용하여 커서의 위치에 따라 왼쪽 스택, 오른쪽 스택 사이에서 문자를 적절히 이동시켜주며 처리해주면 된다.

예를 들어 커서를 왼쪽으로 한 칸 옮긴다면 스택 s의 맨 위 문자를 스택 ss의 맨 위로 이동시키면 된다. (코드 참고)

백스페이스의 경우에는 왼쪽 문자를 하나 지우는 것이므로 스택 s의 맨 위 문자를 pop 해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;

    while(T--) {
        string str; cin >> str;

        stack<char> s, ss;

        for(int i=0; i<str.length(); i++) {
            if(str[i] == '<') {
                if(!s.empty()) {
                    ss.push(s.top());
                    s.pop();
                }
            }
            else if(str[i] == '>') {
                if(!ss.empty()) {
                    s.push(ss.top());
                    ss.pop();
                }
            }
            else if(str[i] == '-') {
                if(!s.empty()) s.pop();
            }
            else s.push(str[i]);
        }

        while(!s.empty()) {
            ss.push(s.top());
            s.pop();
        }

        while(!ss.empty()) {
            cout << ss.top();
            ss.pop();
        }

        cout << "\n";
    }
}

 

 

백준 BOJ 24919번 : Inversions Organize

문제 난이도 : Silver III

알고리즘 분류 : 수학

 

2N x2N 배열이 주어질 때, 왼쪽 절반의 I의 수와 오른쪽 절반의 I의 수가 같고, 위쪽 절반의 I의 수와 아래쪽 절반의 I의 수가 같기 위해서 최소 몇 개의 문자를 바꾸어야 하는지 구하는 문제이다.

 

"왼쪽 위 I의 개수 + 오른쪽 아래 I의 개수 = 오른쪽 위 I의 개수 + 왼쪽 아래 I의 개수"가 성립하면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;

    for(int t=1; t<=T; t++) {
        int N; cin >> N;

        int a = 0, b = 0, c = 0, d = 0;

        for(int i=0; i<N*2; i++)
            for(int j=0; j<N*2; j++) {
                char ch; cin >> ch;

                if(ch != 'I') continue;

                if(i < N && j < N) a++;
                else if(i < N && j >= N) b++;
                else if(i >= N && j < N) c++;
                else if(i >= N && j >= N) d++;
            }

        int ans = abs(a - d) + abs(b - c);

        cout << "Case #" << t << ": " << ans << "\n";
    }
}

 

 

백준 BOJ 3280번 : CARDS

문제 난이도 : Bronze I

알고리즘 분류 : 구현, 시뮬레이션

 

N = 3K개의 카드에 1부터 N까지의 숫자가 써있고, 이들을 한 장씩 골고루 나눠서 3개의 묶음으로 나누고, 이들 중 찾는 카드가 어느 묶음에 있는지 말하는 과정을 M번 거쳤을 때 찾는 카드 번호로 가능한 것을 구하는 문제이다.

 

처음에 카드를 나누고 회수하는 순서가 정순인지 역순인지 파악이 안돼서 답이 나올 때까지 가능한 방법대로 모두 구현해봐서 힘들게 답을 찾을 수 있었다.

핵심은 스택을 쓰는 것이 아니라 그냥 벡터를 이용하여 3으로 나눈 나머지가 x가 아닌 나머지 것들에 모두 false로 체크해주는 방식을 사용하면 편하다는 것이다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    vector<bool> v(N+1, true);

    vector<int> u;
    for(int i=1; i<=N; i++) u.push_back(i);

    while(M--) {
        string str; cin >> str;

        int x;

        if(str == "first") x = 0;
        else if(str == "second") x = 1;
        else if(str == "third") x = 2;

        for(int i=0; i<u.size(); i++)
            if(i % 3 != x) v[u[i]] = false;

        vector<int> w;

        for(int j=0; j<u.size(); j+=3) w.push_back(u[j]);
        for(int j=1; j<u.size(); j+=3) w.push_back(u[j]);
        for(int j=2; j<u.size(); j+=3) w.push_back(u[j]);

        u = w;
    }

    for(int i=1; i<=N; i++)
        if(v[i]) cout << i << " ";
    cout << "\n";
}

 

 

백준 BOJ 20906번 : Flip Flow

문제 난이도 : Bronze I

알고리즘 분류 : 구현, 시뮬레이션

 

기준 시간과 모래시계의 모래가 전부 이동하는데 걸리는 시간과 뒤집는 횟수, 그리고 횟수에 걸쳐 모래시계를 뒤집은 시간 목록이 주어질 때 기준 시간을 기준으로 모래가 모두 쏟아지는데 걸리는 시간을 구하는 문제이다.

 

모래는 처음에 아래에 모두 있으므로 홀수 번째 뒤집는 시간에는 모래가 반대로 이동하고, 짝수 번째 뒤집는 시간에는 모래가 원래 있던 위치로 돌아옴을 이용하여 부호를 다르게 하여 값을 계산해주면 된다.

최종적으로 계산할 때도 N의 홀짝성에 따라 값을 그대로 답으로 얻을 것인지, M - val을 답으로 얻을 것인지를 구분해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int K, M, N; cin >> K >> M >> N;

    int x = 0;

    vector<int> v(N+1);
    for(int i=0; i<N; i++) cin >> v[i];

    v[N] = K;

    for(int i=1; i<=N; i++) {
        if(i % 2 == 1) x = min(x + (v[i] - v[i-1]), M);
        else x = max(x - (v[i] - v[i-1]), (int)0);
    }

    if(N % 2 == 0) cout << x << "\n";
    else cout << M - x << "\n";
}