💎 문제
한수는 크기가 2^N × 2^N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.
N > 1인 경우, 배열을 크기가 2^N-1 × 2^N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.
다음 예는 2^2 × 2^2 크기의 배열을 방문한 순서이다.
N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.
다음은 N=3일 때의 예이다.
.jpeg)
💎 입력
첫째 줄에 정수 N, r, c가 주어진다.
ex)
- 2 3 1
- 3 7 7
- 4 7 7
- 10 511 511
💎 출력
r행 c열을 몇 번째로 방문했는지 출력한다.
ex)
- 11
- 63
- 63
- 262143
💎 제한
- 1 ≤ N ≤ 15
- 0 ≤ r, c < 2^N
💎 풀이 방법
분할정복을 이용한 알고리즘 문제였다. 아이디어는 바로 떠올랐고 해결도 쉽겠다고 생각했는데 2시간 정도 걸려서 푼 문제이다,,,ㅠㅠㅠ
아이디어는 Z방향으로 숫자를 읽기 때문에 조각을 최소화시켜서 4개의 타일로 구성될 때까지 나눠서 결과를 도출해 내는 것이다. 따라서 입력에 3 7 7과 4 7 7이 동일한 결과를 보여주듯이 행과 열에 따라서 결과가 정해진다는 것이다. 그러므로 분할정복을 이용하여 4개의 숫자로 구성된 타일이 될 때까지 분할한 후에, 다시 전체의 크기 타일로 합치면서 순서를 더하여 정복하는 문제이다.
분할하는 과정은 4개의 구역으로 구분시키며 분할할 때마다 문제에서 주어진 행 과 열이 어느 위치에 있는지 위치 정보를 vector를 이용하여 저장해준다. 그리고 이 과정은 숫자 타일이 4개만 있을 때 까지만 분할하여 준다. 이는 N번의 의 과정을 거친 후 일 것이다.
vector <int> v(15); // 제한이 15까지이므로 크기가 15인 벡터를 선언하여 분할할 때의 위치 저장(0~3)
.
.
.
void divide(int x, int R, int C){
if(x == 0)
return;
if(r <= R && c <= C){
v[x - 1] = 0;
divide(x - 1, R - pow(2, x - 2), C - pow(2, x - 2));
}
else if(r <= R && c > C){
v[x - 1] = 1;
divide(x - 1, R - pow(2, x - 2), C + pow(2, x - 2));
}
else if(r > R && c <= C){
v[x - 1] = 2;
divide(x - 1, R + pow(2, x - 2), C - pow(2, x - 2));
}
else{
v[x - 1] = 3;
divide(x - 1, R + pow(2, x - 2), C + pow(2, x - 2));
}
}분할이 완료되었다면 전체 크기에서 주어진 행과 열에 위치한 수가 각 분할이 반복되면서 어느 위치에 위치한지 vector에 정보가 담겨져있을 것이다. 결국 이 정보를 이용하여 결과를 만들어가면 되는데 각 위치는 0,1,2,3으로 z모양을 이루고 저장하였기 때문에 각 위치에 따라서 변이 2^i 형태인 정사각형의 넓이를 더해주면서 그 위치에 순서를 확정지을 수 있을 것이다.
쉽게 말해서 분할한 횟수만큼 반복해주면서 Z모양에 맞춰 위치한 vector정보를 차례대로 읽으면서 변이 2^i인 정사각형의 넓이를 더해주는 것이 이 문제의 결과이다!!
void conquer(){
for(int i = 0;i < N;i++){
for(int j = 0;j < v[i];j++){
result += (pow(2,i) * pow(2,i));
}
}
}설명이 너무 어렵게 한 것 같은데,,,4개의 구역을 분할해가면서 4개의 구역을 0~3의 위치로 지정하여 저장된 이 위치들을 활용하여 다시 정복해나가며 결과를 도출하는 문제였다!
💎 전체 코드
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector <int> v(15);
int result = 0;
int N, r, c;
void divide(int x, int R, int C){
if(x == 0)
return;
if(r <= R && c <= C){
v[x - 1] = 0;
divide(x - 1, R - pow(2, x - 2), C - pow(2, x - 2));
}
else if(r <= R && c > C){
v[x - 1] = 1;
divide(x - 1, R - pow(2, x - 2), C + pow(2, x - 2));
}
else if(r > R && c <= C){
v[x - 1] = 2;
divide(x - 1, R + pow(2, x - 2), C - pow(2, x - 2));
}
else{
v[x - 1] = 3;
divide(x - 1, R + pow(2, x - 2), C + pow(2, x - 2));
}
}
void conquer(){
for(int i = 0;i < N;i++){
for(int j = 0;j < v[i];j++){
result += (pow(2,i) * pow(2,i));
}
}
}
int main(int argc, const char * argv[]) {
cin >> N >> r >> c;
int R = pow(2, N - 1) - 1;
int C = pow(2, N - 1) - 1;
divide(N, R, C);
conquer();
cout << result << "\n";
return 0;
}
💎 고민
velog를 작성하면서 처음 풀어본 분할정복 문제였는데 간단하긴 하였으나 너무 오히려 복잡하게 생각하니깐 분할하는 과정에서 z모양의 위치를 저장하는 방법에서 헤맸던 것 같다 ㅠㅠ 그리고 정복과정에서 실수하나 해서 30분 날린 것 같다 에후 ㅠㅠ 문제가 시간제한이 있는 문제여서 무조건 효율적으로 풀어야했기 때문에 분할정복을 이용해서 최소한의 반복만에 결과를 확인하는 문제인게 너무 큰 힌트이지 않나 싶당. 다음에는 더 빠르게 풀어보자!!
화팅!
