[Baekjoon] 2775번 부녀회장이 될테야 (C++, Python)

[Baekjoon] 2775번 부녀회장이 될테야 (C++, Python)

 

목차

 

 

 

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

2775번: 부녀회장이 될테야

 

 

	1호실	2호실	3호실	4호실	...	n 호실
3층	1	1 +(1+(1+2)) =5	1 +(1+(1+2))+ (1+(1+2) +(1+2+3)) =15
2층	1	1+(1+2) = 4	1+(1+2) +(1+2+3) = 10	1+(1+2) +(1+2+3) +(1+2+3+4) = 20		1+(1+2) +(1+2+3) +(1+2+3+4) + ... +(1+2+3+...+n)
1층	1	1+2 = 3	1+2+3 = 6	1+2+3+4=10		1+2+3+...+n
0층	1명	2	3	4		n

 

C++

 

방법 1 - 2020KB, 4ms, 321B

$O(n^3)$ 복잡도를 가지는 초기 코드

 

#include <iostream>
using namespace std;
int main() {    
	int t, k, n, i, l, p;					
	cin >> t;
	while (t--){
		cin >> k >> n;
		int fn[n];
		for (i=0;i<n;i++){
			fn[i] = i+1;
		}
		for (i=0;i<k;i++){ 
			p=0;
			for (l=0; l<n; l++){
				fn[l] += p;
				p = fn[l];				
			}					
		}			
		cout << fn[n-1] << "\n";		
	}
}

 

방법 2 - 1112KB, 0ms, 276B

 

k층 n호실의 개수가 14개 이하로 적은 것을 배열을 이용하여 다 구하고 그 중 하나를 집어내는 방법

 

#include <stdio.h>
int main(){
	int k,n,t,i,j, a[15][15]={0};
	for(i=0;i<15;i++)a[0][i]=i;

	for(i=1; i<15; i++)
	{
		for(j=1; j<15; j++)
		{
			a[i][j] = a[i-1][j] + a[i][j-1];
		}
	}

	scanf("%d",&t);
	for(i=0;i<t;i++){
		scanf("%d %d",&k,&n);
		printf("%d\n",a[k][n]);
	}
}

 

Python 

 

방법 1 - 29056KB, 72ms, 420B

 

T=int(input())
for t in range(T):
    k=int(input()) #층 floor
    n=int(input()) #room Num
    LowfloorList=[x+1 for x in range(n)]
    UpperfloorList=[]
    sumLow=0
    
    for i in range(k):
        for j in range(n):
            sumLow += LowfloorList[j]
            UpperfloorList.append(sumLow)
        sumLow=0
        LowfloorList = UpperfloorList
        UpperfloorList =[]
    
    print(LowfloorList.pop())

 

방법 2

 

import sys

t = int(sys.stdin.readline())
arr = [[-1 for _ in range(15)] for _ in range(15)]
arr[0] = [i for i in range(15)]
for i in range(1, 15):
	for j in range(15):
		arr[i][j] = sum(arr[i-1][:(j+1)])

for _ in range(t):
	k = int(sys.stdin.readline())
	n = int(sys.stdin.readline())
	print(arr[k][n])

 

방법 3 - 29200KB, 72ms, 268B

 

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    k = int(input())
    n = int(input())
    s = [i for i in range(n + 1)]
    
    for i in range(k):
        for j in range(1, n + 1):
            s[j] = s[j] + s[j - 1]
    print(s[-1])