Backrooms Hill

문제

체감 난이도: 1600

풀이

홀수 번째 있는 원소들은 홀수 번째라면 어느 위치로도 이동할 수 있고, 짝수 번째에 위치해 있는 원소들도 마찬가지입니다.

먼저 $1$ 부터 순서대로 배치해 봅시다. 만약 $1$ 이 맨 왼쪽이나 오른쪽 끝에 위치하지 않는다면 이보다 작은 원소를 끝에 배치해야 하는데, 그런 원소는 존재하지 않으므로 $1$ 은 항상 끝에 위치해야 합니다.

$1$ 을 끝에 배치하고 나면 $2$ 부터 $n$ 까지 남아있는 문제가 되고, 이 때도 마찬가지로 $2$ 는 남은 위치 중 가장자리에 배치해야만 합니다.

문제의 구조가 재귀적이므로 DP를 이용해서 해결할 수 있습니다.

DP를 하면서 $i$ 를 배치할 때마다 양끝 중 하나에 배치할 수 있느냐를 판단해야 하는데, 이는 가장자리에 $i - 1$ 까지 배치하고 나서 남은 자리 중 첫 번째 자리가 짝수 번째인지 홀수 번째인지를 저장함으로써 판단할 수 있습니다.

$DP[i][p]$ 를 $i$ 까지 배치했고 남은 자리 중 첫 번째 자리의 인덱스를 $2$ 로 나눈 나머지가 $p$ 인 경우가 가능한지로 정의합시다.

$DP[i - 1][p]$ 가 참인 경우에만 아래 규칙에 따라 갱신해주면 됩니다.

$n - i + 1$ 이 홀수인 경우
$i$ 의 위치는 $p$ 와 홀짝성이 일치하는 경우에만 양쪽 끝에 배치할 수 있습니다. ( $DP[i][0] = DP[i][1] = \text{true}$ )
그렇지 않으면 양쪽 어디에도 배치할 수 없습니다.
짝수인 경우
$i$ 의 위치가 $p$ 와 홀짝성이 일치하는 경우 맨 앞에 놓으면 되고, ( $DP[i][(p + 1) \bmod 2] = \text{true}$ )
그렇지 않으면 맨 뒤에 놓으면 됩니다. ( $DP[i][p] = \text{true}$ )

코드

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n;
    cin >> n;
 
    vector<int> pos(n + 1);
    for (int i = 1; i <= n; i++) {
        int b;
        cin >> b;
        pos[b] = i;
    }
 
    vector<vector<bool>> dp(n + 1, vector<bool>(2));
    dp[0][1] = true;
    for (int i = 1; i <= n; i++) {
        for (int p = 0; p < 2; p++) {
            if (not dp[i - 1][p]) continue;
 
            if ((n - i + 1) % 2 == 1) {
                if (pos[i] % 2 == p) {
                    dp[i][0] = dp[i][1] = true;
                }
                continue;
            }
 
            if (pos[i] % 2 == p) dp[i][p ^ 1] = true;
            else dp[i][p] = true;
        }
    }
 
    if (dp[n][0] or dp[n][1]) cout << "YES\n";
    else cout << "NO\n";
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
 
    while (t--) solve();
 
    return 0;
}

풀이

홀수 번째 있는 원소들은 홀수 번째라면 어느 위치로도 이동할 수 있고, 짝수 번째에 위치해 있는 원소들도 마찬가지입니다.

먼저

1

부터 순서대로 배치해 봅시다. 만약

1

이 맨 왼쪽이나 오른쪽 끝에 위치하지 않는다면 이보다 작은 원소를 끝에 배치해야 하는데, 그런 원소는 존재하지 않으므로

1

은 항상 끝에 위치해야 합니다.

1

을 끝에 배치하고 나면

2

부터

n

까지 남아있는 문제가 되고, 이 때도 마찬가지로

2

는 남은 위치 중 가장자리에 배치해야만 합니다.

문제의 구조가 재귀적이므로 DP를 이용해서 해결할 수 있습니다.

DP를 하면서

i

를 배치할 때마다 양끝 중 하나에 배치할 수 있느냐를 판단해야 하는데, 이는 가장자리에

i - 1

까지 배치하고 나서 남은 자리 중 첫 번째 자리가 짝수 번째인지 홀수 번째인지를 저장함으로써 판단할 수 있습니다.

DP[i][p]

를

i

까지 배치했고 남은 자리 중 첫 번째 자리의 인덱스를

2

로 나눈 나머지가

p

인 경우가 가능한지로 정의합시다.

DP[i - 1][p]

가 참인 경우에만 아래 규칙에 따라 갱신해주면 됩니다.

n - i + 1

이 홀수인 경우

i

의 위치는

p

와 홀짝성이 일치하는 경우에만 양쪽 끝에 배치할 수 있습니다. (

DP[i][0] = DP[i][1] = \text{true}

)
그렇지 않으면 양쪽 어디에도 배치할 수 없습니다.

짝수인 경우

i

의 위치가

p

와 홀짝성이 일치하는 경우 맨 앞에 놓으면 되고, (

DP[i][(p + 1) \bmod 2] = \text{true}

)
그렇지 않으면 맨 뒤에 놓으면 됩니다. (

DP[i][p] = \text{true}

)

코드

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n;
    cin >> n;
 
    vector<int> pos(n + 1);
    for (int i = 1; i <= n; i++) {
        int b;
        cin >> b;
        pos[b] = i;
    }
 
    vector<vector<bool>> dp(n + 1, vector<bool>(2));
    dp[0][1] = true;
    for (int i = 1; i <= n; i++) {
        for (int p = 0; p < 2; p++) {
            if (not dp[i - 1][p]) continue;
 
            if ((n - i + 1) % 2 == 1) {
                if (pos[i] % 2 == p) {
                    dp[i][0] = dp[i][1] = true;
                }
                continue;
            }
 
            if (pos[i] % 2 == p) dp[i][p ^ 1] = true;
            else dp[i][p] = true;
        }
    }
 
    if (dp[n][0] or dp[n][1]) cout << "YES\n";
    else cout << "NO\n";
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
 
    while (t--) solve();
 
    return 0;
}

Backrooms Hill

문제

풀이

코드

댓글

Backrooms Hill

문제

풀이

코드

댓글