[알고리즘] 백준 9095번 1,2,3 더하기 DP

안녕하세요, 감자코딩에 감자개발자입니다.

이번에 살펴볼 알고리즘 문제는 백준알고리즘 9095번 1,2,3 더하기 문제입니다.

2*n 타일링 문제에 이어서 저희가 공부해왔던 DP를 활용하여 풀면 아주 쉽게 풀 수 있습니다.

문제를 바로 살펴보죠.

1. 문제

1, 2, 3 더하기 성공

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율

1 초 128 MB 27599 17489 11935 62.006%

문제

정수 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 

3

4

7

10

예제 출력 1 

7

44

274

문제를 살펴보면, 1,2,3을 더하여 합으로 나타내는 방법의 수를 출력하라는 말이 있습니다.

이제 살짝 느낌이 오시나요? DP문제에 접근하는 문제들의 유형들이 대부분 이렇습니다.

2. 문제 해결 방법

1) 정수 N이 들어 올 경우 1,2,3을 활용한 합의 경우의 수를 구하라는 문제네요.

2) 정수 N에서 DP를 써서 1이 되는경우 2가 되는 경우 3이 되는 경우의 수를 구하고 그 값을 그때 리턴 받으면 그 값들이 Recursive 재귀호출 되면서 값들이 반환 되겠지요?

- 1일 경우 갈 수 있는 경우의 수 : 1개

[1] 가지 경우 입니다.

- 2일 경우 갈 수 있는 경우의 수 : 2개

[1,1] [2] 

2가지 경우 입니다.

- 3일 경우 갈 수 있는 경우의 수 : 4개

[1,1,1], [1,2], [2,1], [3]

결국 총 N개를 DP로 놓으면 DP = N이 성립되게 됩니다.

N에서 1으로 가는 경우의 수를 표현하면 N-1

N에서 2으로 가는 경우의 수를 표현하면 N-2

N에서 3으로 가는 경우의 수를 표현하면 N-4가 됩니다.

따라서 DP = [N-1] + [N-2] + [N-4] 일 경우를 재귀 호출하게 되면

N 값이 4가 들어 오게 되면 최종적으로 1,2,3 을 만났을 경우 그 값을 리턴하게 된다면 그 경우의 수들이 모두 저장되게 되겠지요?

따라서, DP = [N-1] + [N-2] + [N-4]를 이용하여 TOP-DOWN방식으로 문제를 풀어보겠습니다. 타일링 문제랑 거의 다를 것이 없습니다.

3. 코드 리뷰

//

//  1,2,3 더하기.cpp

//  beakjoon_algorithm

//

//  Created by kgh on 13/04/2019.

//  Copyright © 2019 kgh. All rights reserved.

//

#include <stdio.h>

#include <iostream>

using namespace std;

int dp[11];

int recursive(int n){

    

    // 1의 경우의 수

    if(n == 1){

        return 1;

    }

    // 2의 경우의 수

    if(n == 2){

        return 2;

    }

    // 3의 경우의 수

    if(n == 3){

        return 4;

    }

    // 메모이제이션

    if(dp[n]){

        return dp[n];

    }

    // 재귀 호출

    dp[n] = recursive(n-1) + recursive(n-2) + recursive(n-3);

    return dp[n];

    

}

int main(void){

    int t=0;

    cin >> t;

    // TEST CASE

    while(t--){

        int n;

        cin >> n;

        int result = recursive(n);

        cout << result << "\n";

        

    }

    return 0;

}

타일링 문제에 이어 1,2,3 더하기 문제도 백준 9095번 문제도 살펴보았습니다.

지금 까지의 과정을 잘 따라오신분이라면 이번 문제도 수월하게 푸셨을것이라고 생각합니다.

이상 감자코딩에 감자개발자였습니다.

잘못된 부분이 있다면 댓글을 남겨주세요. 피드백은 사랑입니다