[Baekjoon/백준] 9095 JAVA

문제 출처: https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

 

1. 문제 접근방식

- 1부터 경우의 수를 생각해가며 규칙을 찾았다.

ex)

1 = 1 → 1개

2 = 1+1, 2 → 2개

3 = 1+1+1, 1+2, 2+1, 3 → 4개

4 = 1+1+1+1, 1+1+2(* 3), 1+3(* 2), 2+2 →7개

5 = 1+1+1+1+1, 1+1+1+2(* 4), 1+1+3(* 3), 1+2+2(* 3), 2+3(* 2) → 13개

 

N 일 경우 N-3, N-2, N-1의 개수를 합한 값과 같다.

 

 

2. 내가 푼 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class boj9095 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            System.out.println(sol(N));
        }
    }

    static int sol(int i) {
        if (i == 1)
            return 1;
        else if (i == 2)
            return 2;
        else if (i == 3)
            return 4;
        else
            return sol(i - 3) + sol(i - 2) + sol(i - 1);
    }
}

 

3. 결과 및 느낀점

- 역시 한 번에 감이 안 잡힐 때는 직접 써가면서 하는 방법이 좋은 것 같다.