백준 1074번

재귀 문제 일단 코드부터 

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(__dirname + '/input.txt').toString().split('\n')

input = input[0].split(' ').map(value => +value)

let quard; // 사분면을 나타내는 변수
let result = 0; // 결과값을 나타낼 변수 

function solution(N, r, c, result) {
    let half = 2 ** (N - 1);
    if (N === 0) {
        return result;
    }
    if (r < half && c < half) {
        quard = 1; // 사분면 1사분면 이라는 의미
    }
    else if (r < half && c >= half) {
        quard = 2;
        c -= half; 
    }
    else if (r >= half && c < half) {
        quard = 3;
        r -= half;
    }
    else if (r >= half && c >= half) {
        quard = 4;
        r -= half;
        c -= half;
    }
    result += (half ** 2) * (quard - 1) 
    return solution(N - 1, r, c, result)
}
console.log(solution(+input[0], +input[1], +input[2], result));

일단 종료 조건부터 N이 0이라면 크기가 1x1인 배열이라서 몇번째 방문할것도 없이 그냥 0이라서 종료조건이고 

코드를 찬찬히 살펴보자면 quard는 사분면을 나타내는 변수로 쓰임 예를 들어 quard가 1이면 1사분면 이런식으로 

result는 결과 값을 나타내는 변수고 if문의 의미가 무엇이냐면 입력으로 주어진 (r,c) 값에 따라서 어디 사분면에 위치하는지 정해주는 역할인데 

이런식으로 사분면 위치를 나누고 half라는 변수 즉 원래 변수 2의 N 제곱의 절반을 나눈 값을 기준으로 r과 c 값을 비교해서 사분면 위치를 정해준다 그리고 return 으로 

return solution(N - 1, r, c, result)

이렇게 주는데  예를 들어서 (4,7) 위치를 구한다고 하면 크기가 N-1 일때도 똑같이 (4,7)을 r과 c에 줘버린다면 제대로 된 

위치가 안구해 질것이다 따라서 중간중간 만약 half 값보다 r이나 c가 크다면 half 만큼 빼주고 구해주는 것이다  

그러면 (4,7) 위치가 (0,3)이 되면서 잘 구해질수 있는것임 이 역할을 하는 코드가 r -= half; c -= half; 이 코드들이다.

result += (half ** 2) * (quard - 1)

다음으로 이 코드는 예를 들어 (3,4,7) 이렇게 주어졌을때 처음으로 분할을 했을때 (4,7)은 제 4분면이 된다 

제 4분면은 48부터 시작을 하는데 이 48이라는 값이 어캐 나온거냐면 저 result 코드로 나오게 된것이다 

result에 48을 더하는 이유가 구하고자 하는 동그라미 위치가 제 4분면에 위치해 있기때문에 일단 그전에 경우의 수들은 일일히 구할 필요없이 현재 동그라미가 위치해 있는 사분면에 시작하는 값을 더해주고 또 분할을 해서 더하고 이런식으로 결과값을 구해가는 과정이다 첫번째 분할 후 r,c는 (0,3)이 되고 (0,3)은 N이 2일때 제 2사분면에 위치해 있고 

2사분면은 4부터 시작을 하니 4를 또 더해준다 또 두번째 분할후 (0,1)이 되고 N이 1일때 제 2사분면에 위치해 있으니 1을 더해주면 결과값인 53이 잘나오는 것을 볼수 있다 

 

이러한 이유 때문에 입력으로 주어진 변수는 3개이지만 result 라는 변수를 하나 주어서 결과값을 출력할 수 있게끔 해주는 것이다.,

 

22.09.21 수정 -> 다시 풀다가 굳이 result 변수를 주어야 할까? 라는 의문이 들어서 빼고 제출을 해봤는데 맞았다고 

나와서 굳이 안써줘도 될듯? 

 

이번 문제 너무 어려웠다 늘 어려웠지만 블로그를 보는데 일단 js로 해결한 블로그가 몇개 없고 그마저도 설명이 빈약해서 뭔소리인지 못알아먹고 그래서 파이썬으로 된 설명을 보는데 뭔가 이해가 갈것 같으면서 안가고 그래서 답답하다가 

유튜브에 검색했는데 파이썬으로 푼 영상이 있어서 보는데 이해가 잙 가는건 아닌데 여태 본 블로그들 설명과 조합해서 보니까 이해가 가서 다행이도 굳이었다! 

내일 다시 한번 풀어봐야 겠다