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

Approach

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

문제 조건에 따르면 아파트는 14층(1 ~ 14)까지 있으며,

각 층마다 14호(1 ~ 14)까지 있다.

추가적으로 각 층마다 인원수 처리를 위해 0층에 i 호에는 i명이 산다.

 

• apart[층][호] → apart[15][15] 정도의 크기를 지닌다.

• 0 층의 각 i호는 i명이 산다. → apart[0][i] = i

    ex) apart[0][1..14] = {1, 2, 3, ..., 13, 14}

• 각 층의 i 호에 사는 사람은 아래 연산 결과와 동일하다.

    → apart[floor][i-1] + apart[floor-1][i]

• 각 층의 1호에는 1명씩만 산다. → 이는 apart[floor][0] = 0 값 이용

    ex) apart[floor][1] = 1;

 

아파트 입주민이 한번 주어지고 Test Case마다 구성이 변하지 않기 때문에

각 TC마다 아파트 입주민 수 연산을 하지 않고 LookUp Table로 미리 구성해둔다.

📌 [알고리즘] 시간 성능 향상을 위한 코드 최적화 (C/C++)

[알고리즘] 시간 성능 향상을 위한 코드 최적화 (C/C++)

 

구성해둔 LookUp Table에서 TC에서 요구하는 값을 바로 출력한다.

구성한 LUT는 printState() 함수를 통해 아래 결과를 확인할 수 있다.

void printState()
{
    // 아파트 형태를 위해서 고층부터 출력
    for (int floor = TOTAL_FLOOR; floor >= 0; floor--)
    {
        printf("[%8d층]: ", floor);
        for (int col = 1; col <= FLOOR_HOUSE; col++)
        {
            printf("%8d ", apart[floor][col]);
        }
        printf("\n");
    }
}

 

제출 코드

#include <iostream>

using namespace std;

const int TOTAL_FLOOR = 14;
const int FLOOR_HOUSE = 14;
int apart[15][15];
int TC, r, c;

void makeLUT()
{
    
    for (int col = 1; col <= TOTAL_FLOOR; col++)
    {
        apart[0][col] = col; // 0층 처리
    }


    // 1..14층별 1..14호 까지 인원처리
    for (int floor = 1; floor <= TOTAL_FLOOR; floor++)
    {
        for (int col = 1; col <= FLOOR_HOUSE; col++)
        {
            apart[floor][col] = apart[floor - 1][col]  + apart[floor][col - 1];
        }
    }
}



int main()
{
    // freopen("input.txt", "r", stdin);
    makeLUT();
    // printState();


    cin >> TC;
    for (int i = 0; i < TC; i++)
    {
        cin >> r >> c;
        cout << apart[r][c] << endl;
    }
}