[백준 2775] 부녀회장이 될테야 [C++]

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

2775번: 부녀회장이 될테야

 

1. 해설

 

 다이나믹 프로그래밍(DP)의 쉬운 버전이라고 생각합니다. 사실 이 문제 만큼 다이나믹 프로그래밍이 별 거 없다! 를 표현할 수 있는 문제는 없을 것 같아요. 피보나치 수열은 말이 거창해서 진입장벽이 좀 높지 않나... 그러다면 다이나믹 프로그래밍이 무엇인가? 이름은 거창하지만 간단하게 설명해보자면

 

 전의 값으로 현재의 값을 결정하는 방법

 

 이라고 생각해요. 더 간단하게는 재귀가 아니라 점화식을 사용하는 것이죠. 배열로 표현해보자면 arr[i] = arr[i-1] + j 이런 식으로 배열의 이전값을 사용해서 현재의 배열의 값을 결정하는 방식이라고 생각합니다. 생각보다 별 거 없죠? 

 

 하여튼 문제를 보면 어찌됐든 입력에 따라 값이 변하지 않습니다. 1층 3호 입력을 받든 6층 3호 입력을 맏든 1층 2호의 값은 변하지 않습니다. 그렇기 때문에 한 번에 입력해두고 출력할 때 그 인덱스만 찾아 출력하면 돼요. 그래서 저 같은 경우는 함수를 val_insert()로 아예 빼두었습니다. 배열에 값을 넣어두고 한 번에 출력하려고요.

 

 그리고 해설... 일단 다이나믹 프로그래밍은 제 생각에 배열의 전값으로 현값을 결정하는 것 같습니다. 이번 문제도 그런데, 일단 그림으로 그려 이해하는 게 쉬울 거라 생각합니다. 보시죠!

 

1층 3호를 구할 때의 표

3층 3호를 구할 때의 표

 

 그렇습니다. 1번부터 보시면 1층 2호는 0층 1호 + 0층 2호의 값입니다. 그리고 1층 3호의 값은 0층 1호 + 0층 2호 + 0층 3호의 값이죠. 더 간단히 하면 1층 2호 + 0층 3호의 값이죠. 왜냐? 1층 2호에는 이미 0층 1호와 2호의 값이 더해져 있으니까요. 2번도 역시 보시면 마찬가지입니다. 그래서 결국은 i층 j호를 구하려면 i층 j - 1호 + i - 1층 j호를 해주면 됩니다. 아아 쉬워! 아이 간단해!

 

2. 풀이

 

#include <iostream>
using namespace std;

int dp[15][15];

// 배열에 값을 대입하는 함수
// 입출력은 없다
void val_insert(void){

  // 층수
  for(int i = 0; i < 15; i++){
  	// 호수
    for(int j = 0; j < 15; j++){
    
      // 만약 0층이라면 0층의 호수를 채움
      if(i == 0){
        dp[i][j] = j + 1;
      }
      
      // 0층이 아니라면
      else{
      	// 만약 1호라면 1대입
        if(j == 0){
          dp[i][j] = 1;
        }
        // 아니라면 아래층 호수 + 옆 호수
        else{
          dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
        }
      }
    }
  }
}

int main(void){
  
  // 횟수 입력
  int n;
  cin >> n;
  
  // 배열 입력 함수 호출
  val_insert();
  
  // 횟수만큼
  for(int i = 0; i < n; i++){
  	// 층 - f, 호수 - r 입력
    int f, r;
    cin >> f >> r;
    
    // 출력(f는 0부터 시작이지만 r은 1부터 시작되기 때문에 -1)
    cout << dp[f][r - 1] <<'\n';
  }
}

 

 

 생각보다 어려운 것 같지만 생각보다 간단한 문제죠. 어떤 입력 값이 들어와도 호수의 결과 값은 고정이고, 점화식으로 식을 표현할 수 있다는 사실에만 익숙해지시면 간단하게 풀릴 문제라고 생각합니다. 아마 비슷한 문제를 몇 개 더 풀어보시면 더 이해가 되리라고 생각해요. 코딩 테스트 준비하시는 분들이나 이제 시작하시는 분들 모두 화이팅입니다~!