[재귀, DP] 백준 9095 1,2,3 더하기 c++, java 풀이

BOJ 9095번 1,2,3 더하기 c++ 및 java 풀이

• 난이도: 실버3
• 백준 9095 1,2,3 더하기
  
  
  

문제 정리

1. 어떤 수 N이 주어질때 1,2,3의 합으로 N을 나타낼 수 있는 방법의 개수를 구하여라.
2. 1+2+1 과 2+1+1은 다른 방법이다
3. N은 양수이며 11보다 작다.
   
   
   

문제 접근

재귀를 이용해서 풀면 되겠다고 생각하였습니다.
1,2,3으로 모두 빼면서 0이 될때까지 재귀를 이용해 빼보는 것입니다.
예를들어

4-1 = 3
3-1 = 2
2-1 = 1
1-1 = 0
(1,1,1,1)

4-2 = 2
2-1 = 1
1-1 = 0
(2,1,1)

와 같이 됩니다

문제 풀이

1. 테스트 케이스 수를 입력받습니다.
2. N을 입력받고 N에서 1뺀 수, 2를 뺀 수, 3을 뺀 수를 재귀함수에 넣어서 0으로 만듭니다.
3. 0으로 정상적으로 만들어졌다는 것은ㄴ 1,2,3을 이용해 잘 더해졌다는 의미이므로 ans를 1 증가시켜 만들 수 있는 경우임을 체크합니다.
4. 만약 계속 빼다가 0보다 작아졌다면 1,2,3을 조합해서 만들 수 없는 경우이므로 return 합니다.
   예를들어 N=4일때, add(n-2)-> add(n-3)을 타고 들어갔다면 2+3=5이므로 이미 N을 넘었습니다. 이때 뺐으므로 0보다 작아졋으므로 이는 더해서 만들 수 없는 경우입니다.
   
   
   

DP로 문제 풀기

이 문제는 DP로 분류되어 있는 만큼 DP로도 풀 수 있습니다.
1을 만드는 경우는 1개
2를 만드는 경우는 2개
3을 만드는 경우는 4개 입니다.
그러면 4를 만드는 경우는 몇개일까요???
예시에도 나와있듯이 7개입니다. 뭔가 보이지 않나요???
네 바로 4개를 만드는 경우의 수는 1 + 2 + 4 = 7 입니다.
이 규칙을 찾아내셨다면 DP를 이용해 풀 수 있습니다. 피보나치와 같습니다

백준 9095 1,2,3 더하기 DP c++ 코드

#include <iostream>
#include <algorithm>    // sort와 unique 사용
#include <vector>
using namespace std;

int N;
int cache[12];

void add() {

}

int main() {
    // IO 속도 향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin >> T;
    cache[1] = 1;
    cache[2] = 2;
    cache[3] = 4;

    for (int i = 0; i < T; i++) {
        cin >> N;

        if (cache[N] != 0) {
            cout << cache[N] << endl;
        }
        else {
            for (int j = 4; j <= N; j++) {
                cache[j] = cache[j - 1] + cache[j - 2] + cache[j - 3];
            }
            cout << cache[N] << endl;
        }
    }

    return 0;
}

백준 9095 1,2,3 더하기 재귀 java 코드

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

class Main {
    static int ans;
    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());
            add(N-1);
            add(N-2);
            add(N-3);
            System.out.println(ans);
            ans = 0;
        }
        br.close();
    }

    public static void add(int n){
        if(n < 0) return;
        if(n == 0){
            ans++;
            return;
        }
        add(n-1);
        add(n-2);
        add(n-3);
    }
}

 

풀이 인증

맨 아래부터 C++ 재귀, 자바 재귀, C++ DP, 자바 DP 입니다

c++은 둘다 0ms로 비교 불가이고 자바도 그리 차이나진 않네요 애초에 N이 작아서