[BaekJoon 2775][🟤1] 부녀회장이 될테야

❓ 문제

백준 2775 - “부녀회장이 될테야”

🎯 난이도

Bronze 🟤1

🧠 풀이

1. 내 풀이 (DP + 누적합)

- 알고리즘

• Dynamic Programming

- 설명

2차원 배열을 이용한 DP 풀이이다.

각 층과 각 방들을 하나의 배열의 요소로 생각해 2차원 배열을 만들고, 모든 방들의 값들을 누적합으로 구해서 미리 테이블을 만들어 놓았다. 그렇게 해서 입력이 들어올 때마다 바로 배열에 '임의 접근'으로 값을 출력할 수 있었다.

테스트 케이스가 얼마나 많이 들어올지 모르기 때문에 이 방법이 가장 효율적이라고 생각했다.

미리 테이블을 만드는데는 k * n번의 루프가 필요하지만, 답을 출력하는데는 O(1)의 시간 복잡도를 가진다.

- 코드

내 풀이 코드

#include <iostream>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iT{};
    cin >> iT;

    int arr[15][14]{};

    for(int i = 0; i < 14; ++i)
    {
        arr[0][i] = i + 1;  // 0층 채우기
    }

    // 14 * 14의 모든 배열 미리 구하기
    for(int i = 1; i < 15; ++i)
    {
        for(int j = 0; j < 14; ++j)
        {
            if(j == 0)
            {
                arr[i][j] = 1;
                continue;
            }

            arr[i][j] = arr[i][j - 1] + arr[i - 1][j];
        }
    }

    while(iT--)
    {
        int iK{}, iN{};
        cin >> iK >> iN;

        cout << arr[iK][iN - 1] << "\n";
    }

    return 0;
}

---

2. 추가 풀이 (최적화된 DP)

- 알고리즘

• Dynamic Programming

- 설명

1차원 배열만을 사용한 DP 방식이다.

나의 2차원 배열을 사용하는 방법에 비해 메모리를 절반으로 아낄 수 있다. 그 대신 입력이 들어올 때마다 다시 계산을 해야해서 테스트 케이스의 수가 커지거나, 'k', 'n'의 값이 커질 경우 속도가 확 떨어질 수 있다는 단점도 존재한다.

단 한 번만 답을 내서 출력해야하거나 조건값이 크지 않은 경우에는 최적의 방법이라고 볼 수 있다.

입력이 들어올 때마다 다시 값을 계산해야 하므로 O(k * n)이지만, 각각의 값이 크지 않아 거의 O(1)이라고도 볼 수 있다.

- 코드

내 풀이 코드

#include <iostream>

#include <vector>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iT{};
    cin >> iT;

    while(iT--)
    {
        int iK{}, iN{};
        cin >> iK >> iN;

        vector<int> vecDP(iN + 1, 0);
        for(int i = 0; i <= iN; ++i)
        {
            vecDP[i] = i;   // 0층 채우기
        }

        // 층을 올려가며 각 층의 방 순서에 따라 DP로 값 갱신
        for(int iFloor = 1; iFloor <= iK; ++iFloor)
        {
            for(int iRoom = 1; iRoom <= iN; ++iRoom)
            {
                vecDP[iRoom] += vecDP[iRoom - 1];
            }
        }

        cout << vecDP[iN] << "\n";
    }
}

---

💭 후기

DP라는 동일한 알고리즘을 사용하더라도 각각 어떻게 다르게 풀 수 있는지를 알 수 있는 문제이다.

처음엔 규칙을 이용한 점화식을 만들어서 완전한 O(1)의 방법이 없을까 고민했지만, 생각보다 복잡하고 DP 방식이 더 직관적이고 속도도 충분히 빠르기에 위와 같은 방식으로 풀게 되었다.

🔗 참고자료

• 동적 계획법