백준 1074 Z

내 사고과정과 캐치 못한거 써서 깃헙에 올리기

바킹독님 재귀 강의 참고

https://blog.encrypted.gg/943?category=773649

#include <iostream>
using namespace std;

int func(int n, int r, int c);
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int n, r, c;
    cin >> n >> r>>c;
  
    cout<<func(n, r, c);
    return 0;
}

int func(int n, int r, int c) {
 
    int half= 1 << (n - 1);
    //int half=2^(n-1);과 1<<(n-1);은 무슨 차이?
    //pair를 쓸까?
    //4분할의 시작점
    /*    pair <int, int> d1 = {0,0};
    pair <int, int> d2={0, dely};
    pair <int, int> d3 = { delx, -dely };
    pair<int, int>  d4 = { 0, dely };*
    4분할로 영역을 나눈다.
    영역을 옮길때마다 숫자가 더해지는 방식*/
    //영역 분할하면 영역에 따라 숫자가 어떻게 변하는지 봐야한다.
    //barkingdog님 강의에서 영역분할에 따라 어떻게 숫자(몇 번째인지)가 달라지는지
    //관찰했어야 하는데 그걸 못봤다.
    if (n == 0) return 0;
    if (r < half && c < half) return func(n - 1, r, c);
    if (r < half && c >= half) return half * half + func(n - 1, r, c - half);
    if (r >= half && c < half) return 2 * half * half + func(n - 1, r - half, c);
    return 3 * half * half + func(n - 1, r - half, c - half);
    //n=k일 때, n-1=k-1의 함수의 값을 불러주기 위해서 2,3번째 인자를 영역에 따라 조절해준다.

}

틀린 이유)

47393093번 : n,r,c 순서 틀림

추가 제출 부분에서 int half=2^(n-1);로 다시 바꾸고 base condition은 밑에다 뒀더니 틀렸다.

baescondition의 위치(맨 위인지 몇번 사각형인지 조건문 3~4개 앞인지)는 문제가 안된다.

int half=2^(n-1);은 틀렸고 int half=1<<(n-1);은 맞는 표현이다 왜 그런가?

 

윤성우 열혈 C언어 비트 연산자 부분 참고

p.92~95

C/C++에서는 ^연산자가 비트단위 XOR 연산자로 사용된다.

XOR는 같으면 0을 반환, 다르면 1을 반환한다.

0^0이면 0을 반환

0^1이면 1을 반환 

1^0이면 1을 반환

1^1이면 0을 반환

 

2^(n-1)에 n=2가 들어가면

10

01

최종적으로 11을 반환해서 3이 된다. 그래서 우리가 얻고 싶은 n=2일 때, 2의 (n-1)승의 값 2가 나오지 않는다는 문제점이 있다.

C/C++에서 2의 (n-1)승을 구하고 싶으면 1을 왼쪽으로 n-1비트만큼 움직여준다. 1<<n-1