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

일단 내가 DP에 좀 취약한 것 같으니

DP는 우선순위를 좀 미뤄두고, 다른 문제 유형들을 익히는 것부터 좀 해야겠다.

이건 뭐 시간이 너무 오래걸려서 다른 공부를 할 수가 없으니.

그리고 일단 코딩테스트에서 문제를 보면 어떻게 푸는지 감이라도 잡아야되니깐

내일부턴 다른 유형들 좀 살펴보는 걸로.

 

1. 타일 채우기 3

문제 링크

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 n = Number(input[0]);
    const f = new Array(1000001).fill(0);
    const g = new Array(1000001).fill(0);

    f[0] = BigInt(1); f[1] = BigInt(2);
    g[0] = BigInt(0); g[1] = BigInt(1);
    
    for(let i = 2; i <= n; i++) {
        g[i] = ((f[i - 1] + f[i - 2]) % BigInt(1000000007) + g[i - 2]) % BigInt(1000000007);
        f[i] = (f[i - 2] + (BigInt(2) * g[i]) % BigInt(1000000007)) % BigInt(1000000007);
    }

    console.log(f[n].toString());
});

BigInt 쓰는거 극혐..

이제 타일채우기 문제는 그만 풀어야겠다.

f(n)과 g(n)으로 나눠서 푸는 풀이법이 가장 이해가 잘 되서, 이 풀이를 적었는데

사실 정작 내가 풀 때 이런 풀이를 생각할 수 있을까에 관해선 의문..

이 분 개 천재인듯..

 

2. 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() {
    const N = Number(input[0]);
    
    const g = new Array(1000001).fill(0);

    const queue = [];
    function bfs(x) {
        if(x === 1) return 0;

        g[x] = 0;
        queue.push(x);

        while(queue.length > 0) {
            const cur = queue.shift();

            if(g[1] !== 0) return g[1];

            if(cur % 3 === 0) {
                if(cur / 3 >= 0 && g[cur / 3] === 0) {
                    g[cur / 3] = g[cur] + 1;
                    queue.push(cur / 3);
                }
            }

            if(cur % 2 === 0) {
                if(cur / 2 >= 0 && g[cur / 2] === 0) {
                    g[cur / 2] = g[cur] + 1;
                    queue.push(cur / 2);
                }
            }

            if(cur - 1 >= 0 && g[cur - 1] === 0) {
                g[cur - 1] = g[cur] + 1;
                queue.push(cur - 1);
            }
        }
    }

    console.log(bfs(N));
});

일단, 문제를 보자마자 숨바꼭질이 생각나서 바로 BFS로 풀어봤는데 역시나 잘 풀렸다.

근데 DP로 풀면 코드가 훨씬 짧아진다고 한다.

그래서 DP 답도 한 번 봤는데 사실 이런 DP적인 사고의 코드를 바로바로 짜내는 건 아직까지 무리가 있다.

솔직히 이해하는 데는 별로 무리가 없는데, 맨땅에 바로 이런 코드를 짜내라고 하면 좀 막힌다.

역시 DP는 나랑 안 맞는걸로.

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 N = Number(input[0]);
    const d = new Array(1000001).fill(0);

    d[1] = 0;
    for(let i = 2; i <= N; i++) {
        d[i] = d[i - 1] + 1;
        if(i % 2 === 0) d[i] = Math.min(d[i / 2] + 1, d[i]);
        if(i % 3 === 0) d[i] = Math.min(d[i / 3] + 1, d[i]);
    }

    console.log(d[N]);
});

약점에 미련을 두지 말지어다...허허

신경쓸 게 얼마나 많은데 말이야!