백준 문제 풀이 - 부녀회장이 될테야 2775번

📜 문제 이해하기

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.
이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.
아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

💡 문제 재정의

핵심> a층의 b호에는 (a-1)층의 1호부터 b호까지 사람들의 수만큼 존재한다.
즉, 아래와 같다.
2층 1 4 10 20 35
1층 1 3 6 10 15
0층 1 2 3 4 5

✏️ 계획 수립

이번 문제는 이차원 배열로 풀어도 되지만 좀 더 문제를 효율적으로 풀기 위해 1차원 배열로 문제를 해결하기로 했다.
먼저 위 표를 보면 다음과 같은 규칙을 찾을 수 있다.
<<1층이상 2호 이상에서는 자신의 방 인원수는 왼쪽과 아래층의 인원의 합이다.>>
위 규칙은 점화식으로 생각하면 쉽게 예상할 수 있다. 현재 방의 인원은 자신의 방까지 아래의 모든 방의 합이기 때문에 결국 새로 더해질 방과 여태까지 더해져왔던 방을 더하면 된다는 방법이다.
즉, 코드 구현은 1차원 배열로 자신의 왼쪽 사람과 오른쪽 사람을 구하는 것이 핵심이다.
자신의 왼쪽 사람은 단순히 -1을 하면된다. 이 때 주의할 점은 자신이 1호에 거주한다면 왼쪽을 더해서는 안된다.
자신의 아래 사람은 자신의 인덱스에서 n만큼을 빼주면 된다. 이 때 0층의 사람들은 이 과정을 거치면 안된다.

💻 계획 수행

//
// Created by ventu on 2021-11-10.
// 백준 2775번

#include <iostream>
#include <vector>

using namespace std;


int main() {
    int N;
    int k, n;
    vector<int> people;

    cin >> N;

    int result[N];

    int left, down, now;
    for (int i = 0; i < N; i++) {
        cin >> k;
        cin >> n;

        for (int j = 1; j <= k * n + n; j++) {
            now = 0;
            left = j - 1;
            down = j - n;

            if (down > 0)
                now += people[down - 1];
            else
                now += 1;

            if (j % n != 1 && n != 1)
                now += people[left - 1];

            people.push_back(now);
        }
        result[i] = people.back();
        people.clear();
    }

    for (int l = 0; l < N; l++)
        cout << result[l] << endl;
    return 0;
}

🤔 회고

처음에는 수학적 계산을 통해 배열없이 구하려고했지만 결국 시간을 너무 많이 잡아먹어 실패했고, 2차원 배열대신 1차원 배열을 쓰는것으로 마음먹고 코드를 만들었다. 어떠한 수학적 연산이 있다면 아주 빠르게 연산할 것 같지만 아직까지는 모르겠다.