부녀회장이 될테야 풀이

문제 링크: https://www.acmicpc.net/problem/2775

백준 기본 수학 1 6단계 - 2775번 부녀회장이 될테야를 풀어보았다.

 

풀이: 입력이 들어올 때마다 구하면 시간초과가 나기에, 입력이 들어오기 전에 미리 다 구해놓아야 한다.

 

C++

#include <iostream>

using namespace std;
int aprt[15][15]={0}; 
int main()
{
  for(int j=0;j<15;j++) // 0층에 있는 사람 구함
  {
    aprt[0][j]=j+1;
  }
  for(int a=1;a<15;a++) // 1층부터 14층까지
  {
    for(int b=0;b<15;b++) // 0호부터 14호까지
    {
      for(int c=0;c<=b;c++) // 어느 호에 몇 명이 사는지 계산
      {
        aprt[a][b]+=aprt[a-1][c];
      }
    }
  }
  int t;
  cin>>t;
  for(int i=0;i<t;i++)
  {
    int k,n;
    cin >> k;
    cin >> n;  
    cout << aprt[k][n-1]<<"\n"; // 출력
  }
}

Python

apt=[[0 for col in range(15)] for row in range(15)] # 몇층 몇호에 몇명이 사는지 미리 구해놓는다
apt[0]=[x+1 for x in range(15)]
for i in range(1,15):
	for j in range(15):
		for k in range(j+1):
			apt[i][j]+=apt[i-1][k]
t=int(input())
for i in range(t):
	k=int(input())
	n=int(input())
	print(apt[k][n-1]) # 0층은 있지만 0호는 없기에 k는 그대로 두고 n은 1을 뺀다

Java