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

난이도 : S3

Link  : https://www.acmicpc.net/problem/9095

Tag : DP

 

문제 탐색하기 

- 정수 n이 주어졌을때 n을 1,2,3의 합으로 나타내는 경우의 수를 구하여라

시도 1 ( 실패 😓)

떠오른 문제 해결 방법

DP는 점화식이 떠오르지 않으면 풀기가 어려운것 같습니다.

계속해서 생각해봤지만 점화식을 찾지 못하여 힌트를 보았습니다.

 

시도 2 ( 성공 😲)

떠오른 문제 해결 방법

힌트는 다음과 같았습니다.

4 = ?

1+1+1+1, 3+1, 2+1+1, 1+2+1

1+1+2, 2+2

1+3

 

보이시나요? 맨 뒷자리를 제외한 숫자를 보면서 점화식을 찾았습니다. 

바로 맨뒤에 1로 고정한다면 3의 경우의수와 같고, 동일하게 2로 고정한다면, 2의 경우의수와 같고, 마지막 3으로 고정한다면 경우의수는 1과 같아습니다.

그렇기에 테이블 D[i] i 를 1,2,3의 합으로 나타내는 방법의 수라고 정의한다면

d[4] = d[3] + d[2] + d[1] 입니다.

동일하게 다른 숫자도 결국에 1,2,3만을 더할 수 있기에 점화식은 다음과 같습니다.

d[i] = d[i-1] + d[i-2] + d[i-3] 

점화식이 나오면 구현 난이도는 낮았습니다. 

( d[5]까지 계산한다음 규칙을 찾을 수 있었지만 명확한 근거를 제시하지 못하여 해결하지 못하였었습니다😓)

 

 

시간복잡도⏰

O(N)의 시간복잡도를 가지고 n은 11이하이기 때문에 시간내에도 충분하였습니다.

 

구현 방법 

세부 구현 사항

1. 주어진 값을 입력받는다.

2. i=4부터 점화식을 통해 계산한후 d[i]에 저장한다.

3. i가 목표 n에 도달했을 경우 d[i]를 출력한다.

4. 테스트 케이스 개수 T만큼 반복한다. (단, cusor 변수를 사용하여 최대로 계산된 지점을 기록하면서, n이 cursor보다 작거나 같으면 이미 그전 케이스에서 계산했기 때문에 바로 출력한다.) 

 

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

class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int[] d = new int[12];
        d[1] = 1;
        d[2] = 2;
        d[3] = 4;
        int cur = 3;
        for (int c = 0; c < t; c++) {

            int n = sc.nextInt();
            if (n <= cur) {
                System.out.println(d[n]);
                continue;
            }

            for (int i = cur + 1; i <= n; i++) {
                d[i] = d[i - 1] + d[i - 2] + d[i - 3];
            }

            System.out.println(d[n]);
            cur = n;
        }
    }
}

마무리

자주 풀면서 점화식을 구할 수 있도록 머리를 쓰자!