[백준 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의 합으로 나타내는 방법의 수를 출력한다.

 

 

솔루션

• 몇 가지 숫자를 표현해보면 규칙을 찾을 수 있다.
  • 1을 표현할 수 있는 방법의 개수는 1.
  • 2를 표현할 수 있는 방법의 개수는 2.
  • 3을 표현할 수 있는 방법의 개수는 4.
  • 4를 표현할 수 있는 방법의 개수는 7.
• 따라서 n 표현 방법 개수 = (n - 1) 표현 방법 개수 + (n - 2) 표현 방법 개수 + (n - 3) 표현 방법 개수 와 같은 점화식을 세울 수 있다.

 

Code

1, 2, 3을 이용하여 정수 n을 표현하는 방법을 구하는 함수

public static int ExpressionSum(int n) {
    if(n < 0)
        return 0;
    
    if(n == 0)
        return count[n] = 1;
    
    if(count[n] != 0)
        return count[n];
    
    return count[n] = ExpressionSum(n - 1) + ExpressionSum(n - 2) + ExpressionSum(n - 3); 
}

 

메인 함수

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
 
    int T = Integer.parseInt(br.readLine());
 
    while ((T--) > 0) {
        int n = Integer.parseInt(br.readLine());
        count = new int[n + 1];
        
        ExpressionSum(n);
        
        sb.append(count[n] + "\n");
    }
    
    bw.write(sb.toString() + " ");
    bw.flush();
    bw.close();
    br.close();
}

 

결과