[백준 / BOJ] - 2775번 부녀회장이 될테야 C++ 풀이

---

 

백준 - 단계별로 풀어보기 [2775] 

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

문제

 

a층의 b호에 살려면 (a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 하는 아파트가 있다.

아파트는 0층부터 시작하며, 0층의 i호에는 i명이 산다.

 

Test Case의 개수와 층수 k, 호수 n이 주어질 때, 몇명이 살고 있는지를 출력하는 프로그램을 작성하는 문제이다.

 

풀이

 

먼저 호수는 최대 14호까지이므로, 15*14 이차원 배열을 생성한다.

그 후, 반복문을 통해 아파트의 주민수를 모두 구한다.

 

    for(int i = 0; i < 14; i++)
        people[0][i] = i+1;
    for(int i = 0; i < 14; i++)
    {
        for(int j = 0; j < 14; j++)
        {
            sum += people[i][j];
            people[i+1][j] = sum;
        }
        sum = 0;
    }

 

아파트의 주민수가 모두 구해진 후엔, 입력받은 층과 호수를 통해 바로 출력만 해주면 된다.

 

코드

 

#include <iostream>
using namespace std;

int main() {
    int num,sum = 0;
    cin >> num;
    int *k = new int[num];
    int *n = new int[num];
    int people[15][14] = {0,};
    for(int i = 0; i < 14; i++)
        people[0][i] = i+1;
    for(int i = 0; i < 14; i++)
    {
        for(int j = 0; j < 14; j++)
        {
            sum += people[i][j];
            people[i+1][j] = sum;
        }
        sum = 0;
    }
    for(int i = 0; i < num; i++)
    {
        cin >> k[i];
        cin >> n[i];
    }
    for(int i = 0; i < num; i++)
    {
        cout << people[k[i]][n[i]-1] << '\n';
    }
    return 0;
}

 

 

평가

 

이번 문제는 규칙성을 찾기보다는, 0층의 사람 수가 정해졌기 때문에, 아파트 전체의 모양을 먼저 구하고 찾는 것이 더 빠르다고 생각했다. 우선 층과 호수의 수가 14가 최대이기때문에, 연산시간이 초과가 될 가능성이 적었고 테스트 케이스가 여러개 이기 때문에 매번 계산을 하는것보다 오히려 아파트 호수 전체의 수를 미리 구하는것이 더 빠를 수도 있다고 가정하였다.

 

문제의 정답률은 58%로, 단순 반복문을 통한 해결이 가능한 문제이기 때문에 정답률이 낮지 않았던 것 같다.