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

뚝딱이 공학도·2022년 1월 11일
0

문제풀이_백준

목록 보기
14/159





문제


나의 첫번째 답안

T=int(input())

def floor(a,b):
    s=0
    if a==0:
        return b
    for i in range(b,0,-1):
        s+=floor(a-1,i)
    return s

for i in range(T):
    k,n=int(input()),int(input())
    print(floor(k,n))

자신의 층을 기준으로 '아래층의 1호부터 n호까지 사람들의 수를 합한 만큼의 사람을 데려와야 한다'라는 조건에 재귀함수를 생각했다.
따라서 함수 floor를 선언해 테스트케이스 수 만큼 반복 호출하도록 하였다.
그러나 백준에서는 재귀함수 사용 시 시간초과가 나는 경우가 많다고 한다..
따라서 해당 코드를 재귀함수를 사용하지 않는 방식으로 수정하고자 하였다.



나의 두번째 답안

T=int(input())
for i in range(T):
    k,n=int(input()),int(input())
    s=[i for i in range(1,n+1)] #리스트 생성, 1호~n호
    for a in range(k): #층
        for j in range(1,n): #호
            s[j]+=s[j-1]    #각 호에 거주하는 사람 수 합
        #print('s:',a,'층',s)
    print(s[-1])    #마지막 수(=총 거주 수)

이번에는 재귀함수 대신 리스트를 사용하도록 수정하였다.
1호부터 입력받은 호(n)를 저장할 수 있도록 리스트를 생성하였다.
이후, 각 층마다 1호~n호에 접근하여 각 호에 거주하는 사람 수의 합을 구하였다.
마지막으로 print(s[-1])로 배열의 마지막 인덱스에 접근하여
각 층에 거주하는 전체 사람의 수를 출력하도록 하였다.

0개의 댓글