[BOJ] 1074_Z

Z

문제 링크: https://www.acmicpc.net/problem/1074

1074번: Z

 

문제를 보면 2^N의 2차원 배열이라는 낚시글로 시작된다.
시간제한이 0.5초, 메모리 제한이 512MB에서 2차원 배열로 해결할 수 없다.

먼저 1행을 기준으로 열에 대한 규칙을 찾아보자.

 

0열	1열	2열	3열	4열	5열	6열	7열	8열	9열	10열	11열
0	1	4	5	16	17	20	21	64	65	68	69

 

이렇게 나열하고 보니 0열을 기준으로 2^N과 관련이 있어 보였다.
2^N자리에는 (2^N)^2의 값이 들어가 있고, 그 다음에는 이전에 계산했던 2^i 값들이 더해져 나간다.

 

우리는 이러한 방식을 어디선가 접해봤다.
2진법 계산인데, 첫째 자리부터 한 자리씩 올라갈 수록 2^i를 더해나간다.

 

그래서 열의 값들을 이진수로 표현해보니 규칙이 보였다.

(D3 D2 D1 D0) (2)가 있을 때, 각 자리의 제곱의 합임을 알 수 있다.
(D3^2 + D2^2 + D1^2 + D0^2)
예를들어 9열일 경우 9 = (1001)(2)이므로 ((2^3)^2+(2^0)^2) = 65이다.

 

다음은 1열을 기준으로 행에 대한 규칙을 찾아보자.

이 또한 2진법과 관련이 있다고 생각하고, 각 행을 이진법으로 변환 후 숫자를 비교해보았다.

 

0행	1행	2행	3행	4행	5행	6행	7행
0000	0001	0010	0011	0100	0101	0110	0111
0	2	8	10	32	34	40	42

 

이번에는 바로 찾기는 조금 힘들었지만, 계속 정리하다보니 다음의 규칙을 찾았다.

(D3 D2 D1 D0) (2)가 있을 때, 각 자리 i 번째의 값과 2^(i+1)의 곱들의 합임을 알 수 있다.
(D3*2^(3+1) + D2^2^(2+1) + D1^2^(1+1) + D0^2^(0+1))
예를들어 7행일 경우 7 = (0111)(2)이므로 ((2^2)(2^3)+(2^1)(2^2)+(2^0)(2^1)) = 42이다.

 

그 후 r행 c열의 값은 각각 r행과 c열의 합으로 구할 수 있다.

 

따라서, r,c의 값을 이진법으로 변환 후 각각의 규칙으로 값을 구하고 더한 값을 출력한다.

• 정답 코드

    #include<iostream>
    #include<cmath>
    #include<algorithm>
    using namespace std;
  
    string toBinary(int n)
    {
        string r;
        while (n != 0) {
            r += (n % 2 == 0 ? "0" : "1");
            n /= 2;
        }
        reverse(r.begin(), r.end());
        return r;
    }
    long long unsigned int calCol(string col) {
        long long unsigned int decimalNumber = 0;
        int remainder;
        for (int i = 0; !col.empty(); i++) {
            remainder = (col.back() != '0');
            col.pop_back();
            decimalNumber += pow((remainder * pow(2, i)), 2);
        }
  
        return decimalNumber;
    }
    long long unsigned int calRow(string row) {
        long long unsigned int decimalNumber = 0, i = 0, remainder;
  
        for (int i = 0; !row.empty(); i++) {
            remainder = (row.back() != '0');
            row.pop_back();
  
            decimalNumber += remainder * pow(2, i) * pow(2, (i + 1));
        }
  
        return decimalNumber;
    }
  
    int main() {
        int N, r, c;
        cin >> N >> r >> c;
  
        string row = toBinary(r);
        string col = toBinary(c);
        cout << row << " " << col << endl;
  
        cout << calRow(row) + calCol(col) << endl;
  
        return 0;
    }

---