[백준][C++] 1074번: Z <234>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

https://www.acmicpc.net/problem/1074

1074번: Z

생각의 흐름

일단 재귀문제인건 당연하게 느껴진다.

재귀 문제는 항상 "나 안에 나 찾기" 를 한다는 생각으로 접근하다보면 실마리가 보인다.

 

재귀 함수에 들어왔을때, 우리가 원하는 칸에 도착했다면 출력하고 바로 종료시킨다. (종료조건)

if(x == r && y == c) {
    cout << cnt << "\n";
    exit(0);
}

 

이후 우리가 찾는, (r, c)가 범위 안에 있는지 확인하고, 범위 안에 있다면, 해당 범위에서만 재귀를 다시 진행한다.

if(r >= x && c >= y && r < x+len && c < y+len) { // 범위 안에 있는 경우
    int halfLen = len / 2;
    findZ(x, y, halfLen);
    findZ(x, y + halfLen, halfLen);
    findZ(x + halfLen, y, halfLen);
    findZ(x + halfLen, y + halfLen, halfLen);
}else{ // 범위가 아닌경우
    cnt += len*len;
}

만약 해당 범위 안에 있지 않다면 해당 범위의 넓이인 (len * len)만큼 더해주면 된다.

 

나의 코드

#include <bits/stdc++.h>
#include <iostream>

using namespace std;
#define MAX 16

int N;
int MAP[MAX][MAX];
int cnt;
int r, c;

void findZ(int x, int y, int len) {
    if(x == r && y == c) {
        cout << cnt << "\n";
        exit(0);
    }

    if(r >= x && c >= y && r < x+len && c < y+len) {
        int halfLen = len / 2;
        findZ(x, y, halfLen);
        findZ(x, y + halfLen, halfLen);
        findZ(x + halfLen, y, halfLen);
        findZ(x + halfLen, y + halfLen, halfLen);
    }else{
        cnt += len*len;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    cin >> r >> c;

    findZ(0, 0, (1<<N));

    return 0;
}