설탕 배달

문제 링크

https://www.acmicpc.net/problem/2839

코드

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split(' ');
let num = parseInt(input[0]);

const result = (num) => {
    var memo = [0, 0, 0, 1, 0, 1]
    for (var i = 6; i <= num; i++) {
        if (i < 15) {
            memo[i] = Math.max(memo[i - 3] !== 0 && memo[i - 3] + 1, memo[i - 5] !== 0 && memo[i - 5] + 1)
        } else {
            memo[i] = Math.min(memo[i - 3] + 1, memo[i - 5] + 1)
        }
    }
    if (memo[num] === 0) {
        return -1;
    }
    return memo[num]

}
console.log(result(num))

설명

이런 식으로 봉지를 나눌 수 있는데,
설탕이 3,6,9 kg일 때와, 설탕이 5,10,15일 때의 규칙을 찾을 수 있다.
ex) 3-> 3, 6->3+3, 9-> 3+3+3

이를 이용해, 구하고자 하는 설탕에 -3, -5를 한 설탕에서의 봉지 개수를 비교해 더 작은 봉지를 가져와 1을 더한다.

약간의 예외가 존재하는데, 0,1,2와 같이 봉지의 개수가 0개인 경우에는 더 작은 봉지가 무조건 0이 나오기 때문에 15까지는 적어도 봉지의 개수가 1 이상인 경우만 생각해준다.

쉬운 계단 수

문제 링크

https://gywlsp.github.io/boj/10844/

코드

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split(' ');
let n = parseInt(input[0]);

const answer = (n) => {
    let arr = new Array(n + 1);
    for (let i = 0; i < n + 1; ++i) {
        if (i === 1) {
            arr[i] = new Array(10).fill(1)
        } else {
            arr[i] = new Array(10).fill(0)
        }
    }
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < 10; j++) {
            if (j > 0) arr[i + 1][j - 1] = (arr[i + 1][j - 1] + arr[i][j]) % 1000000000
            if (j < 9) arr[i + 1][j + 1] = (arr[i + 1][j + 1] + arr[i][j]) % 1000000000
        }
    }
    return (arr[n].reduce((acc, cur) => acc + cur) - arr[n][0]) % 1000000000
}
console.log(answer(n))

셜명

이 문제는 123, 121과 같이 1개의 차이로만 이루어지는 수의 개수를 반환하는 문제이다.

문제를 해결하기 위해서, 2차원 배열을 만들었다.
배열의 각 요소는 만들 수 있는 개수를 담는다.

그림처럼, 자릿수가 1인 경우, [0,1,1,1,1,1,1,1,1,1]와 같이 배열이 채워지는데,
0으로 시작하는 경우, 예외적으로 계단이 될 수 없기 때문에 0이 들어간다.

만약, 마지막 자리수가 0인 경우 ex)10
한 자리를 추가해서 만들 수 있는 계단 수는 101만 가능하다. [10(-1) 불가능]

유사하게, 마지막 자리수가 9인 경우, ex) 19
한 자리를 추가해서 만들 수 있는 계단 수는 198 뿐이다.