[PS] 99클럽 코테 스터디 22일차 TIL (멀리 뛰기)

문제

문제 링크

설명

입력 값 n 이 주어졌을 때, 1과 2의 합으로만 그 수를 만드는 경우의 수를 구하는 문제

풀이

동적계획법(다이나믹 프로그래밍, DP) : 각각의 경우의 수를 끝자리가 1로 끝나는 경우와 2로 끝나는 경우로 분리해서 적어보면 아래와 같다.

// n = 3
     [2,1]
     [1,1,1]
     [1,2]
// 1로 끝나는 경우: 2개, 
// 2로 끝나는 경우: 1개

// n = 4
   [2, 1, 1]
   [1, 2, 1]
   [1, 1, 1, 1]
   [1, 1, 2]
   [2, 2]
// 1로 끝나는 경우: 3개,
// 2로 끝나는 경우: 2개

// n = 5
   [2, 1, 1, 1]
   [1, 2, 1, 1]
   [1, 1, 1, 1, 1]
   [1, 1, 2, 1]
   [2, 2, 1]
   [2, 1, 2]
   [1, 2, 2]
   [1, 1, 1, 2]
// 1로 끝나는 경우: 5개,
// 2로 끝나는 경우: 3개

생각해보면, 마지막에 1을 더하는 경우의 수는 n - 1 경우의 수와 같다. 마찬가지로 마지막에 2를 더하는 경우는 n - 2 의 경우의 수와 같다.

예를 들어 n = 5일때 1로 끝나는 경우는 n = 4의 케이스에 1만 더해주는 결과이므로 4의 경우의 수와 같고 2로 끝나는 경우는 n = 3 의 케이스에 2를 더해준 결과와 같다. 이를 식으로 나타내면 i(n) = i(n - 1) + i(n - 2) 가 된다.

class Solution {
  public long solution(int n) {
    long answer;
    int[] dp = new int[2001];
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;
    for (int i = 4; i < dp.length; i++) {
      dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
    }
    answer = dp[n];

    return answer;
  }
}

회고

이런 문제는 경우의 수를 적어보면 풀 수 있는 문제이지만, 그래도 점화식이 잘 보이지 않을땐 1로 끝나는 순서, 2로 끝나는 순서 등으로 적어보면 규칙을 발견할 수 있다.