백준 9095 1, 2, 3 더하기 Java

dp문제는 문제를 잘 읽어보고 푸는 방식을 빨리 캐치하는 것이 중요한 것 같다..

나에게는 아직 너무나도 미숙한 능력이다.

이 문제는 마지막에 어떤 수가 올 수 있는지가 중요한 문제 였다.

 

합을 나타낼 때는 수를 1개 이상 사용해야 하고

어떠한 정수n을 1, 2, 3의 합으로만 나타내는 방법의 수를 구하는 문제이다.

 

난 합으로만 나타낸다 길래

n=2 {1+1} 이 끝인 줄 알았다. 하지만

n=2 {1+1, 2}이였다. 내가 멍청한 건가...........맞는듯하다.

 

아무튼 숫자는 1또는 2또는 3밖에 못쓰기 때문에

마지막에 올 수 있는 숫자는 당연 1, 2, 3 이다.

이를 통해 dp[n] = dp[n-1]+dp[n-2]+dp[n-3]이라는 점화식을 세울 수 있다.

물론 내가 생각해내진 못했다. 정답률 62%짜리 문제의 점화식도 세우지 못하는 초보이다.,

변명아닌 변명을 하자면 n이 11보다 작은 양수로 범위가 굉작히 적기 때문에 dp로 안풀어도

정답처리가 되어서 정답률이 높은것일 것이다..... 내가 못해서이다...더 공부해야지..

 

public static void main(String [] args) {
        Scanner scan = new Scanner(System.in);
        int tc = scan.nextInt();
        int [] dp = new int[11];
        
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for(int i=4; i<=10; i++) {
            dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
        }
        
        for(int i=0; i<tc; i++)
            System.out.println(dp[scan.nextInt()]);
    }