백준 2775번 (C++)

www.acmicpc.net/problem/2775

2775번: 부녀회장이 될테야

 

<답안>

#include <iostream>

using namespace std;

int main()

{

    int t,k,n;

    int array[15][15] = {0};

    for(int i=1; i<15; i++)

    {

        array[0][i] = i;

    }

    for(int i=1; i<15; i++)

    {

        array[i][1] = 1;

    }

    for(int i=1; i<15; i++)

    {

        for(int j=2; j<15; j++)

        {

            array[i][j] = array[i][j-1] + array[i-1][j];

        }

    }

    

    cin>>t;

    while(t-->0)

    {

        cin>>k>>n;

        cout<<array[k][n]<<"\n";

    }

    

    return 0;

}

 

<설명>

난 당연히 시간초과가 뜰줄 알고 제출했지만 성공이 떠버려서 당황한 케이스이다

간단하게, 미리 0층 1호 ~ 14호까지 i로 정해주고, 각층 1호를 1로 정한다음

k층 n호 인원수 = (k층 n-1호 인원수) + (k-1층 n호 인원수) 인 셈이다

 

간단하게 이차원배열 array[15][15]를 선언한 다음,

앞의 인덱스는 층수, 뒤의 인덱스는 호수로 사용하는것을 생각한 다음에

0층을 선언 : i = 1 ~ 14 돌리며 array[0][i] = i

각층 1호를 선언 : i = 1 ~ 14 돌리며 array[i][1] = 1

각층의 각호 : i = 1 ~ 14, j =2 ~ 14 돌리며

array[i][j] = array[i][j-1] + array[i-1][j]

 

그렇게 모든 호수의 값을 먼저 계산한 다음, 입력된 t만큼 반복하며

k와 n을 입력받아 array[k][n]을 출력하면 된다