개요
-
입력
첫째 줄에 정수 N, r, c가 주어진다. -
출력
r행 c열을 몇 번째로 방문했는지 출력한다.
접근 방식
-
첫 번째 방식
길이가 length일때 해당 length 사각형 몇개 지나왔는지 벡터에 저장하고 또 쪼개서 해당 사각형을 네개로 나눴을때
그 점이 어느구역에 있는 지 체크해서 나중에 저장한
length* 갯수를 다 더해서 지나온 칸을 계산한다.하지만 해당 점을 구역을 네개로 쪼갰을때 해당 위치를
(몇,몇) 이라고 넘겨줘야 할 지를 모르겠어서 막혔다.이 부분은 [링크] 이 블로그 를 참조하여 완성 했다.
(y, x) 좌표에서 사등분을 하고 해당 length/2길이의 사분면에
그 좌표를 넘겨줄 땐, (y%(length/2), x%(length/2))로
넘겨 주면 된다.
-
두 번째 방식
[링크] 블로그 를 보고 공부한 방법인데,해당 사분면 안에 R행 C열이 있는지 판단하고
있으면 사등분해서 재귀,
없으면 ans변수에 해당 사분면 넓이 더해준다.이게 가능한 이유는 재귀 시,
좌표가 (r,c)가 될 때 답을 출력해서
해당 좌표가 없는 영역들은 무시가 된다.
첫 번째 방식 코드
#include<iostream> //3
//길이가 length일때 length사각형 몇개 지나왔는지 벡터에 저장하고 또 쪼개서 해당사각형을 네개로 나눴을때
// 그 점이 어느구역에 있는 지 체크해서 나중에 저장한 length* 갯수를 다 더해서 지나온 칸을 계산한다.
//하지만 해당 점을 구역을 네개로 쪼갰을때 몇,몇이라고 넘겨줘야할질 모르겟어서 막혔다.
#include<vector>
#include<math.h>
using namespace std;
vector<vector<int>> v;
vector<int> temp;
vector<int> cnt; //first에 length second에 해당 length사각형 몇개 지나왔는지 저장하려 햇으나 그냥 넓이 자체를 넣어주는거로 변경
void input(int& amount,int& r,int& c)
{
int tempinput=0;
cin >> amount;
for (int i = 0; i < amount; i++) {
temp.clear();
for (int j = 0; j < amount; j++) {
temp.push_back(i);
}
v.push_back(temp);
}
cin >> r >> c;
}
void solution(int r,int c,int length ) {
if (length == 1) return; //length가 0이면 return;
if (r < length / 2 && c < (length / 2)) { //r,c가 1사분면
solution(r % (length / 2), c % (length / 2), length / 2);
}
else if (r<length / 2 && c >=(length / 2)) { //r,c가 2사분면
cnt.push_back((length / 2) * (length / 2) * 1); //해당 점이 2사분면에있다면 1사분면에 해당하는 넓이 cnt벡터에 넣어준다.
solution(r % (length / 2), c % (length / 2), length / 2);
}
else if (r >= length / 2 && c < (length / 2)) { //r,c가 3사분면
cnt.push_back((length / 2) * (length / 2) * 2); //해당 점이 3사분면에 있다면 1,2사분면에 해당하는 넓이 cnt벡터에 넣어준다
solution(r % (length / 2), c % (length / 2), length / 2);
}
else if (r >= length / 2 && c >= (length / 2)) { //r,c가 4사분면
cnt.push_back((length / 2) * (length / 2) * 3); //해당 점이 4사분면에 있다면 1,2,3사분면에 해당하는 넓이 cnt벡터에 넣어준다
solution(r % (length / 2), c % (length / 2), length / 2);
}
}
void printans() {
int ans = 0;
for (int elem : cnt) {
ans += elem;
}
cout << ans;
}
int main() {
int amount=0,r=0,c=0;
input(amount,r,c);
int length = pow(2, amount);
solution(r, c, length);
printans();
}두 번째 방식 코드
#include<iostream> //두번째 방법
#include<vector>
using namespace std;
vector<vector<int>> v;
vector<int> temp;
int amount = 0, r = 0, c = 0,ans=0;
void input() //입력값 받는 함수
{
int tempInput = 0;
cin >> amount;
for (int i = 0; i < amount; i++) {
temp.clear();
for (int j = 0; j < amount; j++) {
temp.push_back(i);
}
v.push_back(temp);
}
cin >> r >> c;
}
void solution(int y, int x, int length ) { //몇개 지나왔는지 구하는 재귀함수
if (y == r && x == c) { //만약 y와 x가 쪼개지다가 r행 c열과 같아지면 ans출력후 return
//함수 다끝나고 ans출력하면 r행 c열 다음 부분도 다 ans에 계산해버려서 답 달라짐
cout << ans;
return;
}
if ((y <= r && r < y + length) && (x <= c && c < x + length)) { //r행 c열이 변이 y+length, x+length인 사각형 안에 있을 때, 4등분으로 재귀
solution(y, x, length / 2);
solution(y, x + length / 2, length / 2);
solution(y + length / 2, x, length / 2);
solution(y + length / 2, x + length / 2, length / 2);
}
else
{
ans += length * length; //만약 사분면안에 r,c가 없다면 해당 사분면 넓이 더해주기
}
}
int main() {
input();
solution(0, 0, 1 << amount); //pow함수 안쓰고도 비트연산자를 통해 2^n승 넣어줄 수 있다.
}문풀후생
2의 배수면 비트 연산자를 통해 pow함수를 안써도 되는 팁을
알게되었고, 나머지값을 이용해 4등분 후 해당 사분면에 매칭되는 좌표를 넘겨주는 부분도 알게되었다.
코딩 창고!