백준 9095 번 : 1, 2, 3 더하기

dyii.tistory.com/6

백준 11727 번 : 2*n 타일링2

이 문제를 어떻게 풀어야 하나 고민했었는데, 위의 문제를 하고 나니 문제를 어떻게 풀어야 하는지 감이 왔다.

 

1과 2의 더하는 방법은 아래의 그림처럼 경우의 수가 1과 2 이다.

 

3을 더하는 방식은 

 1 + 1 + 1

 1 + 2

2 + 1

3

이렇게 4가지 방식이 있는데, 이걸 찬찬히 뜯어보면, 

 

초록색 사각형 안에 들어있는 값이 2의 방식임을 알 수 있다.

3 = 1 + 2 이기에, 2를 구하는 방식의 개수를 그대로 가져가면 되는 것이다.

  - 이미 2의 방식에서 (눈에 잘 띄지는 않겠지만) 중복을 고려하였기 때문에 1을 앞, 중간, 뒤 어디에 넣는지 위치를 고려할 필요가 없어 2를 구하는 방식의 개수를 그대로 가져가는 것이다.

        =>   2개

또한 3 = 2 + 1 이기도 하므로,  1을 구하는 방식에서 2를 추가해주는 것이기 때문에 1을 구하는 경우의 수를 그대로 가져간다.

       =>   1개

그리고 3 = 3 + 0으로도 표현을 할 수 있다. 3은 새롭게 등장했기 때문에 1의 값을 가진다.

      =>    1개

그러므로 3을 구하는 방식은 총 2 + 1 + 1 = 4이다.

 

 

4 = 1 + 3      => 4

   = 2 + 2      => 2

   = 3 + 1       => 1

   이므로 3을 구하는 방식과 2를 구하는 방식, 1을 구하는 방식의 개수를 모두 더하면 4의 개수가 나온다.

 

5  = 1 + 4  = 이전에 구한 4를 더한 방식   => 7개

    = 2 + 3      =>  4개

    = 3  + 2     =>  2개 

   1,2,3으로만 구해야 하기 때문에 4일 때는 조금 전에 구한 값을 그대로 넣어주면 된다.

 

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int T  = sc.nextInt();
		int arr[] = new int[12];
		arr[0] = 0;
		arr[1] = 1;
		arr[2] = 2;
		arr[3] = 4;
		for (int i=0;i<T;i++) {
			int n = sc.nextInt();
			for(int j=4;j<=n;j++) {
				arr[j]= arr[j-1]+arr[j-2]+arr[j-3];
			}
			System.out.println(arr[n]);
		}
	}
}