[BOJ][실2][2469] 사다리 타기

문제 링크

문제링크

첫 번째 풀이 : 구현

문제적 남자에서 사다리 타기문제가 나오길래, 사다리 타기의 원리를 찾아보다가 푼 문제입니다. 오랜만에 구현문제 풀어보네요.

알고리즘

사다리 타기 결과에서 꽝이 1명일 때, 어떻게 중복된 꽝이 나오지 않을까요? 원리는 가로선마다 1대1 swap이 되기 때문입니다. 1대1 swap으로만 이동하기 때문에 한 곳에 두명이상이 도착하지 않습니다.

???를 만날 때까지 위에서부터 swap을 해주고, 결과에서도 ???를 만나기 전까지 swap을 해주면서 올라옵니다.

??? 바로 위와 바로 아래의 결과를 비교해서 한 번만 바꾸어서 만들 수 있는지를 확인합니다.

불가능할 때는 이 경우에는 ‘x’(소문자 엑스)로 구성된 길이 k-1인 문자열을 출력 해야합니다.. 문제 잘 읽어야겠습니다. 저는 여기에서 string의 fill constructor를 보고 구현했습니다.

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;

int curr[30]; // 시작 0,1,2,3,4,...
int result[30]; // 결과 3,2,1,5, ... 등
string row[1010]; // r[i][j] : i번째 가로줄의 j번째 길
int main()
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    cin >> m;
    char t;
    for (int i = 0; i < n; i++) {
        curr[i] = i;
        cin >> t;
        result[i] = t - 'A';
    }
    // 위에서부터 ??? 전까지 내려오기
    bool flag = false; // ???를 만났는지 여부
    for (int i = 0; i < m; i++) {
        cin >> row[i];
        if (flag) continue;
        for (int j = 0; j < n - 1; j++) {
            if (row[i][j] == '-') {
                swap(curr[j], curr[j + 1]);
            }
            else if (row[i][j] == '?') {
                flag = true;
                break;
            }
        }
    }
    
    // 아래부터 ??? 직전까지 올라오기
    flag = false;
    for (int i = m - 1; i >= 0; i--) {
        for (int j = 0; j < n - 1; j++) {
            if (row[i][j] == '*') continue;
            if (row[i][j] == '-') {
                swap(result[j], result[j + 1]);
            }
            else if (row[i][j] == '?') {
                flag = true;
                break;
            }
        }
        if (flag) break;
    }
    
    // ???? row 처리
    string ans = "";
    for (int i = 0; i < n; i++) {
        if (curr[i] == result[i]) {
            ans += "*";
        }
        else {
            ans += "-";
            swap(result[i], result[i + 1]);
        }
    }
    

    // 불가능한 경우 
    for (int i = 0; i < n; i++) {
        if (curr[i] != result[i]) {
            cout << string(n - 1, 'x');
            return 0;
        }
    }
    

    // 가능한 경우
    ans = ans.substr(0, n - 1);
    cout << ans;
    return 0;
}

Success Notice: 수고하셨습니다.