[백준] 0919 오늘의 문제 풀이📚

오늘은 재귀 문제를 풀어봤다.

사실 백트래킹을 공부하려고 했는데 재귀쪽은 기초가 하나도 안되어 있다보니

거슬러 거슬러 올라가다 어떻게 기초 재귀문제부터 풀게 됐다..

그냥 감만 잡고 가는 정도로 풀어봤는데 역시나 감잡기는 커녕 시간 허비가 미친 수준;

혼자선 하나도 못 풀었다. 

다 준내 고민하다가 결국 답을 보고 다시 풀어봤다..

 

1. 곱셈

문제 링크

var input = [];
const readline = require('readline');
const fs = require('fs');

const r = readline.createInterface({
    input: process.stdin
});

r.on('line', function(line) {
    input.push(line.trim());
});

r.on('close', function() {
    let [a, b, c] = input[0].split(' ');
    a = BigInt(a);
    b = BigInt(b);
    c = BigInt(c);

    function pow(a, b, c) {
        if(b == 1) {
            return a % c;
        }
        
        let value = BigInt(pow(a, b/BigInt(2), c));
        value = value * value % c;

        if(b % BigInt(2) == 0) {
            return value;
        }   
        return value * a % c;
    }

    console.log(pow(a, b, c).toString());
});

A * B % M = {(A % M) * (B % M)} % M

이라는 성질을 이용해서 푸는 문제였다.

분할정복법으로 숫자를 나눠서 생각해야 하는 문제.

엄청 간단해보였는데 나는 저 성질을 몰랐어서, 식이 이해가 안되서 한참을 해맸다.

 

그리고 문제 자체가, 분할정복법을 타겟으로 만들어서 그런진 모르겠는데

숫자의 범위가 20억을 넘어간다.

그래서, 자바스크립트로 풀기 위해서는 'BigInt'라는 자료형을 사용해야했다.

 

BigInt자료형은 엄청 큰 숫자를 다룰 때 쓰는 자료형이고

일반적인 Number와 함께 연산에 사용될 수 없다. BigInt끼리만 연산해야 함.

다행히도 == 를 이용해서 Number와의 비교는 가능하다.

그리고, 끝에 n이 붙어있기 때문에 이걸 없애주려면 toString 메소드를 이용해 문자열로 바꿔줘야 함.

 

2. Z

문제 링크

var input = [];
const readline = require('readline');
const fs = require('fs');

const r = readline.createInterface({
    input: process.stdin
});

r.on('line', function(line) {
    input.push(line.trim());
});

r.on('close', function() {
    const line = input[0].split(' ');
    const N = Number(line[0]);
    const r = Number(line[1]);
    const c = Number(line[2]);

    function z(n, r, c) {
        if(n === 1) {
            if(r === 0 && c === 0) {
                return 0;
            } else if(r === 0 && c === 1) {
                return 1;
            } else if(r === 1 && c === 0) {
                return 2;
            } else {
                return 3;
            }
        }

        const half = Math.pow(2, n-1);

        if(r < half && c < half) {
            return z(n-1, r, c);
        } else if(r < half && c >= half) {
            return half*half + z(n-1, r, c - half);
        } else if(r >= half && c < half) {
            return 2 * half*half + z(n-1, r - half, c);
        } else {
            return 3 * half*half + z(n-1, r - half, c - half);
        }
    }

    console.log(z(N, r, c));
});

사실 이 정도 문제는 별로 어렵지 않은 문제인 것 같은데

내가 재귀쪽에 자신감이 없어서 그런가, 자꾸 재귀 문제를 풀 때면

풀이를 힐끗힐끗 찾아보게 된다.

 

이정도는 충분히 생각해 볼 법한 문제였는데. 아까비.

 

+) 종료 조건을 b === 1이 아닌 b === 0으로 잡으면 코드가 조금 더 간단해진다.

var input = [];
const readline = require('readline');
const fs = require('fs');

const r = readline.createInterface({
    input: process.stdin
});

r.on('line', function(line) {
    input.push(line.trim());
});

r.on('close', function() {
    const line = input[0].split(' ');
    const N = Number(line[0]);
    const r = Number(line[1]);
    const c = Number(line[2]);

    function z(n, r, c) {
        if(n === 0) {
            return 0;
        }

        const half = Math.pow(2, n-1);

        if(r < half && c < half) {
            return z(n-1, r, c);
        } else if(r < half && c >= half) {
            return half*half + z(n-1, r, c - half);
        } else if(r >= half && c < half) {
            return 2 * half*half + z(n-1, r - half, c);
        } else {
            return 3 * half*half + z(n-1, r - half, c - half);
        }
    }

    console.log(z(N, r, c));
});