알고리즘 문제풀이(Java) - 백준 9095번(1, 2, 3 더하기)

백준 온라인 저지 9095번(Java)

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

동적계획법(DP)를 연습하기위해 기초 문제를 풀어보았다.

재귀를 활용한 동적계획법으로 풀기 위해서 두 가지 관점으로 접근해보았다.

첫번째, 전체 문제를 부분 문제로 나눌 수 있을까?

두번째 , 재귀 함수를 이용하기 위해 규칙을 찾고 이를 통해 점화식을 구할 수 있을까?

노트에 끄적끄적이다보니 어느정도 실마리를 찾을 수 있었다.

예를들어 n = 4일 경우   

1+1+1+1

1+1+2    1+2+1    2+1+1

2+2

1+3    3+1 의 총 7가지이다. 

또 n = 5일 경우          

1+1+1+1+1  

1+1+1+2     1+1+2+1     1+2+1+1     2+1+1+1

1+1+3    1+3+1    3+1+1

2+2+1    2+1+2    1+2+2

의 총 11가지이다.

여기서 밑줄친 부분은 n=4일 때 경우의 수에다 +1만 한 것이다. 즉 n=4일 경우 n=3의 경우의 수를 그대로 갖고온다는 뜻이다. 

이를 통해 전체의 문제를 부분으로 쪼개서 재귀로 구현해야겠다는 생각이 들었다.

 

그렇다면 n=3, n=4, n=5 로 증가하면서 나갈 때 숫자들을 세보았다.(이 숫자가 크지 않아서 일일이 다 세보았는데 좀 더 복잡한 문제면 조금 곤란할 듯 하다..

여기서 내가 찾은 점화식은  f(n) = f(n-1) + f(n-2) + f(n-3) 이다.

점화식을 찾았으니 Base case만 찾기만 하면 된다. 

n은 정수로 입력되지만 n=1 또는 n=2일 경우 f(-1), f(-2) 등 음수 값이 들어간다. 

이를 해결하기 위해서 n이 0이하 일 경우 0을 반환해준다.  

또한 f(1), f(2), f(3)을 BaseCase로 설정을 해주어야 n=4이상일 때 값을 구할 수 있다.

소스코드

package BAEKJOON_Algorithm;
import java.util.Scanner;
 
class A{
    int answer;
    int sumOfonetwothree(int n) {
        // base cases
        if(n<=0)
            return 0;
        else if(n==1 || n==2)
            return n;
        else if(n==3)
            return 4;        
        
        answer = sumOfonetwothree(n-1)+sumOfonetwothree(n-2)+sumOfonetwothree(n-3);
        return  answer;    
    }
}
public class Sum_OneTwoThree_9095 {    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T;// 테스트 케이스의 개수
        int n;// 정수 n
        int answer;// 정답
        T = sc.nextInt();
        A ans = new A();
        for(int i=0; i<T; i++) {
            n = sc.nextInt();
            answer = ans.sumOfonetwothree(n);
            System.out.println(answer);
        }
 
    }
 
}
 

문제를 다 풀고 제대로 푼게 맞나 찾아보니 많은 사람들이 배열에 값을 저장해놓고 풀었다. 값을 1번만 구하면 사실 굳이 배열에 값을 저장해놓고 풀 필요는 없을듯 한데 테스트 케이스의 개수 만큼 반복해서 값을 구해야 하므로 이 경우에는 배열에 값을 저장해 놓고 풀면 더욱 좋을것 같다.