[알고리즘] 백준 15992 1, 2, 3 더하기 7

📖문제

1, 2, 3 더하기 7

❓구상

이 문제는 "1, 2, 3 더하기" 문제 시리즈중 7번째 문제다. 앞서 풀어본 "1, 2, 3 더하기" 문제는 모두 Dynamic Programming 알고리즘 유형이였기 때문에 비슷하게 접근을 해보려했다. 하지만, 여태 풀어본 DP 문제는 피보나치수열처럼 단순히 N번째의 DP 값을 구하면 되는 문제였는데 이 문제 같은 경우는 T개의 테스트 케이스개수가 주어지고, 그 아래로 T개의 n, m 의 쌍이 있다. 즉, 여태 풀어본 DP 문제는 n 과 m 이 주어지는게 아닌 n 이 주어져서 n번째 DP 값을 구하면 되는 문제였는데, 이번에는 1, 2 ,3 을 이용해 만들 수 있는 n의 갯수 + 1, 2, 3 숫자 m 개를 사용해서 n이 되도록 하는 문제인것이다. 어떻게 접근하면 좋을지 생각하다가 문뜩 옛날에 DP 의 패턴을 좀더 쉽게 파악하는 방법을 Chat GPT 에게 물어본 결과 표를 사용해서 각각의 케이스마다 어떤 값을 갖는지를 파악해서 그 값을 비교해 패턴을 파악한 후 점화식을 구하는 방법이 생각났다. 이것을 활용해 각각의 케이스마다 어떤 값을 갖는지 표로 먼저 작성해보기로 했다.

 

패턴파악을 위한 표 작성

N \ M	1	2	3	4	5	6	7	8	9	10
1	1	0	0	0	0	0	0	0	0	0
2	1	1	0	0	0	0	0	0	0	0
3	1	2	1	0	0	0	0	0	0	0
4	0	3	3	1	0	0	0	0	0	0
5	0	2	6	4	1	0	0	0	0	0
6	0	1	7	10	5	1	0	0	0	0
7	0	0	6	16	15	6	1	0	0	0
8	0	0	3	19	30	21	7	1	0	0
9	0	0	1	16	45	50	28	8	1	0
10	0	0	0	10	30	90	77	36	9	1

 

표로 작성해서 각각의 케이스 별 값을 정리한 결과

1. N 과 M 이 같은 경우 → 1개 ( N = 2, M = 2 → 1, 1 의 조합만 가능)
2. N 이 4보다 작고 M 이 1인 경우 → 1개 (1, 2, 3 의 조합이기 때문)
3. N 이 3 인 경우 N - 1 영역에서 M - 1, M - 2 칸의 합이 N, M 의 값이 됨
4. M 이 1보다 큰 경우 N - 1 영역에서 M - 1, M - 2, M - 3 칸의 합은 N, M 의 값이 됨

위 4개의 조건을 바탕으로 코드를 작성해보기로 했다.

 

코드.

const [T, ...arr] = require('fs').readFileSync('./input.txt', 'utf-8').trim().split('\n');
const nums = arr.map(e => e.split(' ').map(Number));
const maxN = [...nums].sort((a, b) => b[0] - a[0])[0][0];
// N 중 가장 큰 값을 구하여 maxN 에 할당
const maxM = [...nums].sort((a, b) => b[1] - a[1])[0][1];
// M 중 가장 큰 값을 구하여 maxM 에 할당
const dp = Array.from({ length: maxN }, () => new Array(maxM).fill(0n));
const DIV_NUM = 1000000009n;
const solution = (n, m) => {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (i === j) {
        dp[i][j] = 1n;
        break;
      }
      else if (i < 3 && j === 0) dp[i][j] = 1n;
      else if (i === 2) dp[i][j] = (dp[i - 1][j - 1] + dp[i - 2][j - 1]) % DIV_NUM;
      else if (j > 0) dp[i][j] = (dp[i - 1][j - 1] + dp[i - 2][j - 1] + dp[i - 3][j - 1]) % DIV_NUM;
    }
  }
}
solution(maxN, maxM);
const result = new Array(+T);
nums.forEach((e, i) => result[i] = dp[e[0] - 1][e[1] - 1]);
console.log(result.join('\n'));

 

백준 예제 입력 1을 기준으로 살펴보면 T 가 3 즉, 테스트 케이스가 3개 있고 각각의 케이스는 사로 다른(같은 값이 존재할수는 있음)

n 과 m 을 갖는다. 단순히 각각의 케이스를 solution 함수에 인수로 넘겨줌으로 문제를 해결 할 수 있지만, 각각의 케이스에서 n과 m 의 각각의 최댓값을 maxN, maxM 으로 설정하여 그 값으로 dp (maxN * maxM 공간을 갖고, 0이 할당되어있는 배열) 배열을 생성해주고 solution 함수에 maxN, maxM 을 인수로 전달하는 방식으로 구현했다.

 

출력

위의 코드로 주어진 케이스 (4, 2), (7, 5), (10, 6) 일때의 결과를 확인할 수있다.

4 2 → 3
7 5 → 15
10 6 → 90

 

🔥배운 점

이번 문제를 해결하면서 이전에는 피보나치 수열을 DP 를 활용하는 문제와 같이 단순한 DP 문제를 해결하는 법에 익숙해 모든 DP 문제 접근법을 단순한 구조로 생각하고 접근했는데 2차원 배열을 활용하면서 좀더 응용된 문제를 해결할 때 좀 더 다양한 접근법을 생각해볼 수있게 되었다. 하지만, 이 문제의 경우 if 조건문 분기를 많이 상용해서 가독성이 떨어지는 문제가 있다.

피보나치 수열을 DP로 해결할때 초기값을 설정했듯 이 문제에도 초기값을 설정할 수 있는 부분을 따로 설정해 조건 분기를 줄이는 방법을 모색해 개선을 해봐야할거 같다.