[백준] 1,2,3 더하기 in Java

📍 문제

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

📍 코드 설명

입력 된 수를 1, 2, 3의 합으로 만들 수 있는 경우의 수를 세는 문제이다.

 

1, 2, 3이 합에서 이용되므로 일단 1, 2, 3을 만들 수 있는 경우의 수를 세보자

 

아직까지는 잘 모르겠으니 5까지 경우의 수를 구해보자

 

엇 이때 어떤 규칙을 알 수 있다

 

n=4를 자세히 보자

 

n=4일때 결국 n=3일때의 경우의 수에 + 1, n=2일때의 값에 + 2, n=1일때의 값에 + 3 을 하면 n=4의 경우의 수와 동일해진다

 

혹시모르니 n=5도 자세히 보자

 

여기서도 동일하게 n=4경우의 수에 +1, n=3의 경우의 수에 +2, n=2 의 경우의 수에 +3을 하면 n=5의경우의수가 나오는 것을 볼 수 있다.

 

이것으로 우리는 n의 경우의 수 = n-3 의 경우의 수 + n-2의 경우의 수 + n-1의 경우의 수 임을 알 수 있다

피보나치 수열과 동일하게 풀 수 있다

📍 코드

✔️ 코드

import java.util.*;
import java.io.*;

class main {
	static public void main(String []args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        int T = Integer.parseInt(st.nextToken());   //테스트 케이스의 개수

        int[] dp = new int[11];

        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for(int i = 0; i < T; i++){
            st = new StringTokenizer(bf.readLine());
            System.out.println(fibo(dp, Integer.parseInt(st.nextToken())));
        }
    }

    static int fibo(int[] dp, int n){
        if(dp[n] != 0){
            return dp[n];
        }else{
            dp[n] = fibo(dp, n-3) + fibo(dp, n-2) + fibo(dp, n-1);
            return dp[n];
        }
    }
}

 

📍 틀린이유

규칙성을 발견하지 못했다ㅠㅠ

규칙만 알면 푸는 건 금방인데 규칙성을 찾는게 아직 경험이 부족한 듯 하다

 

📍 기억할 것

뒤에 2개만 보지말고 넓은 시야로 바라볼것