백준 2775번 <부녀회장이 될테야> - C++

생각

Dynamic Programming인 듯하다

 

이차원 배열을 세우고, arr[0][i]에는 i를 채워둔다

arr[a층][b호] = arr[a-1층][1호] + arr[a-1층][2호] + ... + arr[a-1층][b호]이다

#include <algorithm>
#include <iostream>
#include <math.h> //C
#include <cmath> //C++
#include <string>

using namespace std;

int main() {
  
  int t;
  cin >> t;

  for(int i=0; i<t; i++){
    int k, n;
    cin >> k >> n;
    
    int arr[15][15] = {};
    for(int i=1;i<=14;i++) {arr[0][i] = i;}
    
    for(int j=1; j<=k; j++){

      
      for(int x=1; x<=n; x++){
        for(int l=1; l<=x; l++){
          arr[j][x] += arr[j-1][l];
        }
        //cout << j << "층 " << x << "호 " << arr[j][x] << "명" << '\n';
      }
      
    }
    cout << arr[k][n] << '\n';
  }
  return 0;
}

for문 완전 덕지덕지 발랐는데,.. 어찌 맞긴 맞았다.

 

DP(dynamic programming)이 뭐냐면, 큰 문제를 작은 여러 개의 문제로 쪼개서 푸는 방식이다.

a층b호를 바로 구할 수 없으니, a-1층1호, a-1층2호, ..., a-1층 b호를 구해서 더해주면 a층b호가 된다.

이런 식이다. 음.. 예전에 백준 풀 때 여기서 포기했던 것 같다. 문제가 어려웠던 건 아니지만, 이게 DP문제임을 스스로 깨달았고, 풀어냈다는 점에 일단 의의를 두자.