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

 

안녕하세요? 수구리입니다.

이번 포스팅에서는 단계별로 풀어보기의 2차원 배열 문제를 가져왔습니다.

2차원 배열은 쉽게 말해서 격자모양의 배열이라고 생각하시면 됩니다.

각각의 원소에 접근하는 방식도 일차원 배열과 크게 다를 점이 없습니다.

문제를 풀어보면서 설명을 이어나가겠습니다.

아래는 백준 문제 링크입니다. 문제를 보시고 생각해보고 풀이를 봐주세요!

 

[ 문제 ] 2755: 부녀회장이 될테야

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

2775번: 부녀회장이 될테야

 

 

[ 나의 풀이 ]

#include <iostream>
using namespace std;

int apt[101][15];

int main(){
  // Test Case 입력
  int t; 
  cin >> t;
  
  while(t--){
	// k <= 1, n <= 14  
    int k, n; 
    cin >> k >> n;
      
    for (int i=0; i <= k; i++){
        for (int j=1; j <= n; j++){
            if (i == 0) {
                apt[0][j] = j;
            }
            else if (j == 1){
                apt[i][1] = 1;
            }
            else {
                apt[i][j] = apt[i][j-1] + apt[i-1][j];
            } 
        }
    }
    cout << apt[k][n] << "\n";
  }
}

 

 

 

[ 설명 ]

1. 우선 문제에서 주어진 가장 핵심 조건이 주어지는데

 "a층의 b호에 살려면
자신의 아래(a-1) 층의 1호부터 b호까지
사람들의 수의 합만큼 사람들을 데려와 살아야 한다" 

라는 조건입니다. 위의 조건을 생각해보기 전에,, 이해하기 쉽도록 아파트를 2차원 배열을 표현해 보도록 하겠습니다.

K층	1명			최종!
..
..
2층	1명
1층	1명
0층	1명	2명	...	N명
	1호	2호	..	N호

2. 문제에서 0층의 i호에는 i명이 살고 있으므로 위의 코드에서 i == 0인 경우에 속하며 j값으로 초기화를 합니다.

3. 또 문제의 조건에 의해서 1호에 있는 사람은 모두 1명밖에 살지 못하게 되죠. 위의 코드에서 j == 1인 경우입니다.

4. 나머지 경우에는 생각해보면 K층의 i호에는 바로 아래층인 K-1층의 사람 수와, 같은 층의 바로 이전 호수인 j-1호에 사람 수를 더한 경우입니다. 이 부분이 코드에서는 else 부분에 속하게 됩니다. (위의 표에서는 0층을 아래쪽으로 하였지만, 실제 2차원 배열은 좌상단이 0층임에 유의!)

5. 그럼 결과적으로 우리가 얻고자 하는 K층의 N호까지 반복해서 계산해가면서 최초로 입력한 k와 n값이 같아지는 순간 종료를 하고 그때 2차원 배열에 저장된 최종 값을 출력해줍니다.

 

이상으로 단계별로 풀어보기의 2775번 문제인 2차원 배열 문제: 부녀회장이 될 테야 였습니다.

질문사항이나 더 좋은 풀이가 있을 수 있습니다!

감사합니다!