백준 1074 Z

작성일 | In |

Problem : Z

유형 : 분할 정복

문제 해석

  • 원하는 지점 R, C 에 언제 도착하는지 구하라.

문제 재해석

  • 입력값은 2^N 꼴이 아닌 N 꼴로 들어온다.
  • 2^N 은 사각형 한변의 길이이다.

해결 전략

  • 같은 모양이 반복 되어진다.
  • 재귀적으로 이어지고, 분할 정복으로 해결 해본다.

설계, 구현

쪼개기

  • 원하는 좌표가 나올때까지 절반씩 쪼개나간다.
  • 쪼갠 기준으로 각 사분면에 존재 하는지를 확인하며 계속 진행해 나간다
    • ex ) 3사분면에 존재 한다면, 1,2 사분면은 이미 거쳐온 것이다.

늘려 나가기

  • 원하는 좌표가 나올떄까지 늘려 나간다.
  • 맨 처음에는 무조건 좌표 범위 안에 있을 것이다.
  • 각 사분면안에 존재하는지 찾아본다.
  • 존재 하지 않는다면, 각 사분면의 크기만큼 진행 된 것이다.

디버깅

  • 나누기와 뺴기를 잘못 사용했었다.
  • 좌표 위치는 크기만큼 더하거나 감소 시켜가야 하는데, 나누어 나가는 실수를 했다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>

using namespace std;
int n, findR, findC;


#if 01
// 쪼개기
int Func(int curSize, int r, int c) {
    if (curSize == 0) return 0;

    int half = pow(2, curSize - 1);
    int cnt = half * half;

    if (r < half and c < half) return Func(curSize - 1, r, c);
    if (r < half and c >= half) return cnt + Func(curSize - 1, r, c - half);
    if (r >= half and c < half) return cnt * 2 + Func(curSize - 1, r - half, c);
    return cnt * 3 + Func(curSize - 1, r - half, c - half);
}

void Solve() {
    cout << Func(n, findR, findC);
}

#else

// 늘려 나가기
int answer;
int Func(int len, int r, int c) {
    if (r == findR and c == findC) return answer;

    if (r <= findR and c <= findC and findR < r + len and findC < c + len) {
        if (Func(len / 2, r, c)) return answer;
        if (Func(len / 2, r, c + len / 2)) return answer;
        if (Func(len / 2, r + len / 2, c)) return answer;
        if (Func(len / 2, r + len / 2, c + len / 2)) return answer;
    }

    answer += len * len;
    return 0;
}


void Solve() {
    cout << Func((int)pow(2, n), 0, 0);
}

#endif


void Input() {
    cin >> n >> findR >> findC;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);
    Input();
    Solve();

    return 0;
}

피드백

  • 분명히 과거 풀었던 문제였음에도 불구하고, 고생을 많이 했다.
  • 분할 정복 문제에 아직 많이 약하다.
  • 분할 정복이 코딩 테스트에서는 잘 나오지 않는 유형이나,재귀적 사고력을 높이기에는 이만한 것이 없는것 같다.
  • 더 많은 문제를 풀어보자.