[C++]백준 32175번 컵 쌓기

📌문제 링크

---

https://www.acmicpc.net/problem/32175

📌문제 설명

---

점화식이 바로 보이는 문제입니다. 바텀업으로 O(N * M)에 해결 가능합니다.

📌코드

---

#include <iostream>
#include <algorithm>
#include <vector>
#define MOD 1000000007
using namespace std;

// 동적 계획법을 위한 배열
long long dp[100001];
// 컵의 개수와 높이, 컵 배열
int N, H, cup[101];

// 입력을 받는 함수
void input(){
    cin >> N >> H;
    for(int i = 0; i < N; i++){
        cin >> cup[i];
    }
}

// 문제를 해결하는 함수
void solve(){
    input(); // 입력 받기
    dp[0] = 1; // 초기값 설정
    for(int i = 1; i <= H; i++){ // 높이 1부터 H까지 반복
        for(int j = 0; j < N; j++){ // 각 컵에 대해 반복
            if(i - cup[j] >= 0){ // 현재 높이에서 컵을 뺀 값이 0 이상일 때
                dp[i] += dp[i - cup[j]]; // 경우의 수 더하기
                dp[i] %= MOD; // 모듈러 연산
            }
        }
    }
    cout << dp[H] << '\n'; // 결과 출력
}

int main(){
    ios::sync_with_stdio(0); // 입출력 속도 향상
    cin.tie(0); // 입력 스트림과 출력 스트림 분리
    cout.tie(0); // 출력 스트림과 입력 스트림 분리
    solve(); // 문제 해결 함수 호출
    return 0; // 프로그램 종료
}