[백준(BOJ)] 1074번 : Z - C++[CPP]

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

1074번: Z

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 분할 정복
• 재귀

 

---

 

⊙ 문제 접근 과정

 

이 문제, 상당히 고전했다. 실버 1문제 맞냐?

 

먼저 4등분을 한 후, 행과 열이 몇 번째 칸(1, 2, 3, 4)에 있는지 찾아내자.

숫자를 위와같이 정한 이유는 Z 모양으로 탐색해서이다.

왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서(Z 모양)대로 방문하여 각각 1, 2, 3, 4라고 번호를 붙여줬다.

 

위 그림과 같이 탐색한다.

 

어느 칸에 찾고자 하는 좌표가 있는지 알아낸다면 문제를 해결할 수 있다.

 

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <cmath>

using namespace std;

int N,r,c,ans;

int main() {
    cin >> N >> r >> c;

    int y = pow(2, N)/2;
    int x = y;
    

    while (N-- > 0) {
        int temp = pow(2, N)/2;
        int skip = pow(4, N);
 
        if (r < y && c < x) {
            // 1
            x -= temp;
            y -= temp;
        } else if (r < y && x <= c) {
            // 2
            x += temp;
            y -= temp;
            ans += skip;
        } else if (y <= r && c < x) {
            // 3
            x -= temp;
            y += temp;
            ans += skip * 2;
        } else {
            // 4
            x += temp;
            y += temp;
            ans += skip * 3;
        }
    }
    cout << ans;
}

---

⊙ 결과

 

---

 

 

⊙ 마무리

 

 

재귀...... 분할 정복....

 

좋아요는 로그인하지 않아도 누를 수 있습니다!