BOJ) 1,2,3 더하기

1,2,3 더하기

9095번: 1, 2, 3 더하기

풀이

 

브루트 포스 문제로 입력값 n을 1, 2, 3 숫자의 합으로 나타낼 수 있는 경우의 수를 구하는 문제다.

또한, 순서가 있기 때문에, 1+1+2 와 1+2+1은 다른 것으로 간주한다.

예전에 풀었던 문제인데, 기억에 남아있지 않아서 새롭게 풀었다.

 

먼저, 예전에 풀었던 방식은 점화식을 통해서 답을 찾았었다.

dn = dn-3 + dn-2 + dn-1 이라는 식이 나와서 쉽게 답을 구한 것 같다.

 

새롭게 푼 방식은, 브루트 포스 문제임을 알고 풀어서 재귀를 이용했다.1~3까지 수를 입력받은 n에서 빼면서 0이하가 됐을 때, 종료하는 메소드를 만들었다.이 때, n이 0이라면 1~3을 더해갈 때, n이 나왔다는 소리기 때문에 count를 증가시켜줬다.

 

브루트 포스로도 풀 수 있지만, 점화식을 이용해서 푸는 것이 메모리와 속도에 훨씬 효율적이라고 생각한다.

 

코드 1

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    private static int getResult(int num) {
        if(num ==1) {
            return 1;
        } else if(num ==2) {
            return 2;
        } else if(num ==3) {
            return 4;
        }
        int[] caseNum = new int[11];
        caseNum[0] =0;
        caseNum[1] =1;
        caseNum[2] =2;
        caseNum[3] =4;
        for(int i =4; i<=num; i++) {
            caseNum[i] = caseNum[i-3] + caseNum[i-2] + caseNum[i-1];
        }
        return caseNum[num];
    }
    private static void printCase(int num) {
        System.out.println(getResult(num));
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());
        for(int i=0; i<testCase; i++) {
            int num = Integer.parseInt(br.readLine());
            printCase(num);
        }
        br.close();
    }
}

 

코드 2

 

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

public class Plus123_9095 {
    final static int[] numArr = {1,2,3};
    static int answer;

    public static void main(String[] args) throws IOException {
        solution(new BufferedReader(new InputStreamReader(System.in)));
    }

    private static void solution(BufferedReader br) throws IOException {
        int testCase = Integer.parseInt(br.readLine());

        for(int i=0; i<testCase; i++) {
            answer =0;
            getCount(Integer.parseInt(br.readLine()));
            System.out.println(answer);
        }
    }

    private static void getCount(int n) {
        if(n <=0) {
            if(n ==0) {
                answer++;
            }
            return;
        }
        for(int i=0; i<3; i++) {
            getCount(n-numArr[i]);
        }
    }
}