[백준] DP - 9095번, 1, 2, 3 더하기

* 공부 목표

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

문) 정수 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. 테이블 정의
 - 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타나내는 경우의 수
 - 개수를 입력받는 반복문.
2. 점화식 : D[n] = D[n-3] + D[n-2] + D[n-1]

• 점화식은 단순하다. 피보나치 수열임. (11726, 11727 문제를 떠올리면 쉬움.)
• n=1 / 1 = 1
• n=2 / 2 = (1+1) or (2)
• n=3 / 3 = (1+1+1) or (1+2) or (2+1) or (3)
• n=4 / 7가지 1, 2, 3 각각의 경우의 수를 합한 수와 같다.

3. 초기값 정하기 : D[0] = D[1] = 1

 

코드

BW를 활용해 출력 시 for문과 배열의 사용을 줄이고자 하였음.

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int i=0; i<T; i++) {
            int n = sc.nextInt();
            bw.write(print(n) + "\n");
        }
        bw.flush();
        bw.close();
        sc.close();
    }
    static int print(int n) {
        int[] D = new int[n+1];
        D[0] = D[1] = 1;
        D[2] = 2;
        for(int i=3; i<n+1; i++) {
                D[i] = D[i-3] + D[i-2] + D[i-1];
            }
        return D[n];
    }
}

 

1차 문제 발생

점화식을 도출해내는데 얼마 안 걸렸는데, 여러 번 런타임 에러가 떴다.

512MB 메모리 제한 때문인가... 아니면 백준에서 함수를 못 쓰게 막아둔 것인가... 당황스러웠음.

 

결국 이유는 서칭해서 알게 됐는데, n=초기 값인 경우를 생각하지 못해서였다.

만약 1을 입력할 경우, D[1]까지만 할당받아 D[2]에서 오류가 뜬다.

 

n<2인 경우의 수를 고려하여 다시 코드를 작성하면 다음과 같다.

 

수정 코드(최종)

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int i=0; i<T; i++) {
            int n = sc.nextInt();
            bw.write(print(n) + "\n");
        }
        bw.flush();
        bw.close();
        sc.close();
    }
    static int print(int n) {
        int[] D = new int[n+1];
        D[0] = D[1] = 1;
        if (n<2) {
         return 1;
        } else {
            D[2] = 2;
            for(int i=3; i<n+1; i++) {
                D[i] = D[i-3] + D[i-2] + D[i-1];
            }
        }
        return D[n];
    }
}

 

 

경우의 수를 놓치지 말고 생각해서 쓸데 없는 에러를 피하자!