백준 9095: 1, 2, 3 더하기 - javascript(dp)

문제 출처 

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

9095번: 1, 2, 3 더하기

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

예제 입력 1 복사

3
4
7
10

예제 출력 1 복사

7
44
274

 

문제 풀이 힌트 

N인 정수를 1,2,3으로만 표현해보자. 

 

1일 때, 
 1

2일 때,  
 1+1, 2
3일 때, 
 1+1+1, 1+2, 2+1, 3
4일 때, 
1+1+1+1,

1+1+2, 

1+2+1, 

2+1+2, 

1+3, 

3+1, 

2+2

 

혹시 발견한 규칙이 있나욤? 

규칙은 4일 때부터 발견할 수 있다. 

결론부터 말하자면 

4일 때의 경우의 수는 1일 때 경우의 수 + 2일 때 경우의 수 + 3일 때 경의의 수 를 모두 합한 수가 된다. 

즉, `arr[4] =  arr[1] + arr[2] + arr[3]` 이 된다. 

 

이유)

- 1일 때 가능한 조합 1에서 '3'을 더한것이 1+3의 경우 

- 2일 때 가능한 조합 1+1에서 '2'를 더한 것이 '1+1+2'의 경우 

- 2일 때 가능한 조합 2에서 '2'를 더한 것이 '2+2'의 경우 

- 3일 때 가능한 조합 1+1+1에서 '1'을 더한 것이 '1+1+1+1'의 경우 

- 3일 때 가능한 조합 1+2에서 '1'을 더한 것이 '1+2+1'의 경우 

....등등 

 

 

문제 풀이 코드 

const [N, ...numbers] =  require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(Number); 

function DP(N, numbers){
    let arr = new Array(11); //idx가 0부터 10까지인 배열 생성
    arr[1] = 1; //1일 때 경우 1개
    arr[2] = 2; //2일 때 경우 2개
    arr[3] = 4; //3일 때 경우 4개 
    for(let i=4; i<11; i++){ //4일 때부터 10까지 채워주면 된다. 
        arr[i] = arr[i-3] + arr[i-2] + arr[i-1]
    }
    for(let i=0; i<N; i++){ //test case가 N개이다. 그만큼 출력해주면 된다. 
        console.log(arr[numbers[i]]); 
    }
}

DP(N, numbers);

 

Only 문제 풀이 

const [N, ...numbers] =  require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(Number); 

function DP(N, numbers){
    let arr = new Array(11); 
    arr[1] = 1; 
    arr[2] = 2; 
    arr[3] = 4; 
    for(let i=4; i<11; i++){
        arr[i] = arr[i-3] + arr[i-2] + arr[i-1]
    }
    for(let i=0; i<N; i++){
        console.log(arr[numbers[i]]); 
    }
}

DP(N, numbers);

 

알고가는 ppoint 

1) 문제 푸는 tip: 주어진 예시를 가지고, 규칙을 찾는 것부터 한다. ! 

보자마자 무슨 조합을 해야하나? 이런 고민 전에 규칙이 잇나부터 본다. !

의외로 어렵게 풀기보단, 간단한 규칙이 있을 가능성이 높음. 

2) dp가 선언되기 전에 dp[N] 이런식으로 호출하면 런타임 에러가 뜬다. 

이런식으로 밑에 위치시킨다.