BOJ9095

BaekJoon 9095 : 1, 2, 3 더하기

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

나의 첫번째 답

#include <iostream>

int FindAllCases(int input) {

    // 기본 경우에는 재귀를 사용 X
    if(input == 1)
        return 1;
    else if (input == 2)
        return 2;
    else if (input == 3)
        return 4;
    else    // 그렇지 않을 때는 재귀 O
        return FindAllCases(input-3) + FindAllCases(input-2) + FindAllCases(input-1);

}

int main() {

    int T;      // 테스트 케이스의 갯수
    std::cin >> T;

    int n[T];

    for (int i = 0; i < T; i++)
    {
        std::cin >> n[i];
    }

    for (int i = 0; i < T; i++)
    {
        std::cout << FindAllCases(n[i]) << std::endl;
    }
    
    return 0;
}

천천히 머릿속으로 몇 번 세어보니, 재귀로 풀면 될 것 같았고, 그래서 재귀로 풀었더니 생각보다 금방 풀렸다.

그러나 이렇게하면, 매번 처음부터 다시 계산해야 한다. 구하고자 하는 숫자가 작으면 별 문제 없겠지만, 숫자가 커지면 커질 수록, 그리고 여러 번 반복해서 호출할수록 비효율적이다.

이를 개선해서, 배열 한 곳에 저장하는 방식을 추가해서 코드를 개선해보았다.

두번째 답

#include <iostream>
#include <algorithm>    // max_element() 함수를 쓰기 위해 include

int findAllCases(int input, int* arr) {

    // n이 3보다 큰 경우에만 계산 및 저장
    for (int i = 4; i <= input; i++) {
        arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
    }

    return arr[input];   
}

int main() {

    int T;      // 테스트 케이스의 갯수
    std::cin >> T;

    int n[T];

    for (int i = 0; i < T; i++)
    {
        std::cin >> n[i];
    }

    int max = *std::max_element(n, n+T);
    int store[max] = {0};   // 입력값 중 최대값만큼만 배열을 만들고

    // 기본 경우 초기화
    store[1] = 1; // 1을 만드는 방법은 1가지
    store[2] = 2; // 2를 만드는 방법은 2가지
    store[3] = 4; // 3을 만드는 방법은 1+1+1, 1+2, 2+1, 3 총 4가지

    for (int i = 0; i < T; i++)
    {
        std::cout << findAllCases(n[i], store) << std::endl;
    }
    
    return 0;
}