코딩 테스트 대비 4주 챌린지 JS (1463, 11726, 11727, 9095)

백준 1463번 

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

solution(+input[0]);

function solution(N) {
    const DP = new Array(N + 1).fill(0);
    for (let i = 2; i <= N; i++) {
        DP[i] = DP[i - 1] + 1;
        if (i % 2 === 0) {
            DP[i] = Math.min(DP[i], DP[i / 2] + 1);
        }
        if (i % 3 === 0) {
            DP[i] = Math.min(DP[i], DP[i / 3] + 1);
        }
    }
    console.log(DP[N])
}

첫 dp 문제다 (저번에 풀었는데 기억 안나는거일수도?) 어쨋든 처음이라 나름 구현은 해봤지만 당연히 틀렸고 구글링 해서 설명을 보는데 잘 이해가 안가서 거의 1시간 30분? 동안 해설을 본것 같다. 
일단 배열을 만들어야 하는데 new Array(N + 1).fill(0) 무슨의미냐면 n+1개 만큼 0으로 채운다는 뜻임.

예를 들어 N이 3일때 [0,0,0,0] 이렇게 된다는 뜻 
for문 조건식을 봤을때 왜 2부터 시작하는거지 고민했는데 조건이 주어진 수를 1로 만들기 인데 1부터 해봤자 의미가 없으니 2부터 시작하는 것이었다(빡대갈 수준;)
DP[i] = DP[i - 1] + 1; 이 코드는 무슨의미냐면 예를 들어 DP[2] 일때 2가 되기전에 1에다 +1을 해야 나올 수 있는

수 이기 때문에 dp[1] + 1 = 1이 된다. (+1이라는 것은 연산횟수가 한 번 더해지기 때문에 더한 것이다.) 
참고로 DP[1] = 0 이다. 
그리고 DP[4] 일때는 이때는 2로 나누어 떨어져서 2로 나누어 떨어진다면 2로 나누어준다라는 조건을 이용해서 dp[4] = (dp[4 - 1] + 1, dp[4 / 2] + 1) 이러한 식을 세울수 있는데

근데 왜 빼기 1도 포함인거냐 라고 한다면 어떤 수든 1을 뺄수 있으므로 DP[i] = DP[i - 1] + 1 이 식을 포함 시키는

것이다. 3으로 나누어 떨어지는 수의 경우에도 마찬가지로 포함시켜준다.

그리고 Math.min을 이용해서 1빼기 한거와 2나 3으로 나눈 횟수중 최솟값을 구해준다. 
정리하면서 깨달은건데 처음에 왜 for문을 이용해서 2부터 시작하지 라는 고민을 한 이유가 어차피 주어진수만 대입해서 구하면 되는거 아닌가라는 생각을 했지만 만약 그렇게 한다면 예를 들어 주어진 수가 10일때 1을 빼거나 2로 나누어 떨어지니 DP[10] = (DP[10 - 1] + 1, DP[10 / 2] + 1) 이렇게 하고 나서 값을 구할수가 없는것이다.

왜냐면 DP[10 - 1]가 무슨값인지 모르고 DP[10 / 2]도 마찬가지여서   
근데 for문을 쓴다면 2부터 차근차근 반복문을 돌아서 값을 알아내서 DP[5]도 무슨수인지 값이 나왔을거고

답을 찾을수 있는것이다.  
검색해보니 이게 Bottom-up 방식이라고 한다 간단히 말해서 가장 작은 문제들 부터 답을 구해가며 전체 문제의 답을 찾는 방식 이라는데 아직 잘은 모르겠다.

백준 11726번 & 백준 11727번 

이 두문제는 같이 정리 

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

solution(+input[0]);

function solution(n) {
    const DP = new Array(n + 1).fill(0);
    DP[1] = 1;
    DP[2] = 2;
    for (let i = 3; i <= n; i++) {
        DP[i] = (DP[i - 1] + DP[i - 2]) % 10007;
    }
    console.log(DP[n]);
}

주어진 조건을 보면 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는건데 1×2, 2×1 타일 중에

무엇을 우측에 두냐에 따라서 각각 방법의 수가 달라진다.
우선 n이 1일때는 2x1 이니까 방법은 1가지, n이 2일때는 1×2 타일2개 2×1 타일 2개 이용해서

총 2가지 경우의 수를 나타낸다.
n이 3일때 위에서 말한 것이 나오는데 오른쪽에 2×1 타일이 들어갔을때는 2가지 경우의 수가 나오고 오른쪽에 1×2 타일2개가 있을때는 1가지 경우의 수가 나와서 총 3가지 경우의 수가 존재한다.   
n이 4일때로 가정을 해봐도 마찬가지 
코드를 설명해보자면 배열하나를 만들고 DP[1], DP[2]는 값들이 각각 1,2 니까 미리 선언 해두고 for문을 3부터 시작을 하는것이다. 
위에 규칙을 이용해서 나온 식이 DP[i] = (DP[i-1] + DP[i-2]) 이다 결국 i번째에 놓을 최대 수는 i-1과 i-2에 놓일

최대 수의 합이라는 것을 알수 있다. 

이러한 수를 보고 규칙을 찾을수 있는데 오른쪽에 2×1 타일이 들어갔을때는 n-1개의 경우의 수가 존재 하고 오른쪽에 1×2 타일2개가 있을때는 경우의 수가 n-2개 만큼 존재하는것을 알수 있다

라고 여태 잘못 알고 있었다. 11727번을 풀면서 깨달았는데 밑에 마저 설명하겠음.

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

solution(+input[0]);

function solution(n) {
    const DP = new Array(n+1).fill(0);
    DP[1] = 1;
    DP[2] = 3;
    for(let i=3; i<=n; i++) {
        DP[i] = (DP[i-1] + DP[i-2] + DP[i-2]) % 10007;
    }
    console.log(DP[n])
}

내가 잘못 이해하고 있었다. 그전 문제인 11726번을 이해를 잘 했다 생각했는데 이문제를 풀면서 아니라는 걸 깨닫게 됨.  
무엇을 잘못 이해했었냐면 2×1 타일이 들어갔을때는 n-1개의 경우의 수가 존재 하고 오른쪽에 1×2 타일2개가 있을때는 경우의 수가 n-2개 만큼 존재하는것을 알수 있다 라고 했었는데 그게아니라 
n이 3일때 총 방법의 수는 3개인데 이게 n-1개 n-2개 더한 값이 아니라 n-1에 방법의 수와 n-2일때 방법의 수를

더한 값이란 의미이다. 이게 무슨소리야? 라고 생각할수 있는데 그림으로 예시를 들어봄. 

11727번은 DP[i] = (DP[i-1] + DP[i-2] + DP[i-2]) 이렇게 식이 나오는데 왜 DP[i-2] 이게 2개냐면

2x2 타일과 1x2 타일 2개 짜리 크기가 같기 때문에 방법의 수도 똑같기 때문이다.

단 똑같다고 하나로 치부하면 안되는게 크기만 같은 경우고 타일 종류 자체는 다르기 때문에 이 둘은 다르게 봐야 한다

백준 9095번 

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

const testcase = [];
for (let i = 1; i <= +input[0]; i++) {
    testcase.push(input[i].split(' ').map(value => +value));
}

solution(+input[0], testcase);

function solution(T, testcase) {
    const DP = [0, 1, 2, 4];
    for (let i = 0; i < T; i++) {
        for (let j = 4; j <= testcase[i]; j++) {
            DP[j] = DP[j - 1] + DP[j - 2] + DP[j - 3];
        }
        console.log(DP[testcase[i]])
    }
}

이 문제는 1,2,3 으로 주어진 정수를 나타내는 총 방법을 구하는 건데 1, 2, 3으로 나타내는 방법은 앞의 어떤 수가 오던 뒤에 1, 2, 3을 더한 경우의 수 밖에 없다. 무슨 말이냐면 4를 나타낸다고 한다면 3+1, 2+2, 1+3

이런식으로 1,2,3 이 무조건 온다는 의미이다 
여기서 힌트를 얻을 수 있는데 그전 문제인 타일링 문제처럼 접근하면 되는데 
일단 1을 나타내는 방법은 1가지, 2를 나타내는 방법 2가지, 3은 4가지이다.

여기서 그전 문제처럼 접근할수 있다는 이유가 나온다.

4를 나타내는 방법중 뒤에 1,2,3이 오는 방법은 3+1, 2+2, 1+3 이렇게 3가지인데 여기 3+1에서 3은 앞에서 구한대로

4가지를 나태낼수 있으므로 3+1 4가지가 되는것이고 2+2에서 앞에 2여서 2가지 1+3 1은 1가지 이므로 

총 4+2+1을 한 7가지가 되는것이다. 
어떤 앞의 수에서 끝에 1, 2, 3을 더하는 것이 되므로, 결국은 현재값 -1, 현재값 -2, 현재값 -3의 횟수를 더한 값이 현재값의 총 횟수인 것이다.

회고 

처음으로 풀어본 dp 문제들 이었다. 생각보다 아직까지는 그렇게 어렵진 않은듯

물론 해설을 보고 푸는거긴하지만 해설을 봐도 이해가 안가고 풀기도 싫고 의욕도 떨어지는 문제들이 있어서 그런지

몰라도 할만 한것 같다. 그리고 해설을 보면 전체적인 큰 틀은 비슷한것 같은데 막상 풀려고 하면 못풀겠음 

 

진행률 33/155   대략 21%                         남은 기간 19일 

 
 
실패 다시 시작할 예정

※ 내가 풀면서 못 풀었거나 헷갈려다거나 틀렸다거나 아니면 입출력 문제에서만 해당되는 사항이지만 10분 안에 못 풀었다거나 하는 문제들만 정리한 거임