C++로 주어진 제약 조건에서 행렬의 마지막 값 구하기

문제 소개

N개의 요소로 이루어진 숫자 리스트 A가 있다고 가정해 보겠습니다. 리스트의 모든 요소는 1, 2 또는 3입니다. 이때 행렬 X를 다음과 같이 정의합니다.

X[1][j] = A[j] (단, j는 1부터 N까지)
X[i][j] = |X[i-1][j] − X[i-1][j+1]| (단, i는 2부터 N까지, j는 1부터 N+1−i까지)

우리가 구해야 하는 것은 위 규칙을 끝까지 적용했을 때 얻어지는 행렬의 마지막 값입니다.

예제

입력이 A = [1, 2, 3, 1]이라면 출력은 1이 됩니다. 계산 과정은 다음과 같습니다.

X[1][1] ~ X[1][4] : 1, 2, 3, 1
X[2][1], X[2][2], X[2][3] : |1−2| = 1, |2−3| = 1, |3−1| = 2
X[3][1], X[3][2] : |1−1| = 0, |1−2| = 1
X[4][1] = |0−1| = 1
따라서 최종 답은 1입니다.

문제 해결 접근 방법

이 문제는 인접한 두 값의 차이를 반복해서 계산하는 구조이므로, 비트 시프트와 패리티(parity) 성질을 활용하면 효율적으로 답을 구할 수 있습니다. 풀이 단계는 다음과 같습니다.

1단계: calc() 함수 정의

calc() 함수는 N과 M을 매개변수로 받아 다음 작업을 수행합니다.

cnt를 0으로 초기화합니다.
k를 N으로 설정한 뒤, k가 0이 아닌 동안 k를 오른쪽으로 1비트씩 시프트하면서 cnt := ⌊(cnt + k) / 2⌋를 반복 수행합니다.
k를 M으로 설정한 뒤, 같은 방식으로 cnt := ⌊(cnt − k) / 2⌋를 반복 수행합니다.
k를 N − M으로 설정한 뒤, 같은 방식으로 cnt := ⌊(cnt − k) / 2⌋를 반복 수행합니다.
마지막으로 cnt의 논리 반전값(!cnt)을 반환합니다.

2단계: 메인 로직 구현

n을 배열 A의 크기로 설정하고, 크기가 n + 1인 배열 arr을 준비합니다.
i가 1부터 n − 1까지 증가하는 동안 arr[i − 1] = |A[i] − A[i − 1]|을 계산해 인접 요소 간의 차이를 저장합니다.
n을 1만큼 감소시킵니다.
hh := 1, pd := 0, ck := 0으로 초기화합니다.
i가 0부터 n − 1까지 증가하는 동안 arr[i]가 0이 아니면 다음을 수행합니다.
• arr[i]가 1이면 hh := 0으로 바꾸고 pd ^= calc(n − 1, i)를 수행합니다.
• 그렇지 않으면(arr[i]가 2이면) ck ^= calc(n − 1, i)를 수행합니다.
ck &= hh를 수행합니다.
pd ^ ck가 0이 아니면 "1" + hh를 반환하고, 그렇지 않으면 "0"을 반환합니다.

C++ 구현 예제

다음 구현을 통해 더 잘 이해해 보겠습니다.

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

int calc(int N, int M) {
    int cnt = 0;
    for (int k = N; k; k >>= 1)
        cnt += k >> 1;
    for (int k = M; k; k >>= 1)
        cnt -= k >> 1;
    for (int k = N - M; k; k >>= 1)
        cnt -= k >> 1;
    return !cnt;
}
string solve(vector<int> A) {
    int n = A.size();
    vector<int> arr(n + 1);
    for (int i = 1; i < n; i++) {
       arr[i - 1] = abs(A[i] - A[i - 1]);
   }
   --n;
   bool hh = 1, pd = 0, ck = 0;
   for (int i = 0; i < n; i++)
   if (arr[i]) {
      if (arr[i] == 1)
         hh = 0, pd ^= calc(n - 1, i);
      else
         ck ^= calc(n - 1, i);
   }
   ck &= hh;
   if (pd ^ ck)
   return "1" + hh;
   return "0";
}
int main(){
   vector<int> A = { 1, 2, 3, 1 };
   cout << solve(A) << endl;
}

입력

{ 1, 2, 3, 1 }