백준(Baekjoon) 2775번 : 부녀회장이 될테야

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

2775번: 부녀회장이 될테야

#코드

T = int(input()) #테스트 케이스
for i in range(T):
    k = int(input()) #층
    n = int(input()) #호
    zero_User = list(range(1, n+1))
    for x in range(k):
        for y in range(1, n):
            zero_User[y] += zero_User[y-1] #리스트 안에서 1층 인원수로 교체
    
    print(zero_User[-1]) #리스트의 제일 마지막 출력

 

# 풀이 과정

1. 입력값 확인

T = 테스트 Case
k = 아파트 층 수
n = 아파트 호 수

2. 출력값 확인

k층의 n호 수에서 살고 있는 인원 출력

3. 조건 확인

1. 아파트는 0층 부터 있으며 1호부터 시작한다. 
2. 0층의 인원 수는 각각 n명씩 있다. (n = 아파트 호 수) 
3. k층의 n호에서 살기 위해서는 k-1층의 n호까지의 인원 수를 데리고 살아야 한다.

4. 1차 풀이 (재귀함수 활용 = Fail 시간초과)

def UserCount(Floor, Value):
        if Floor == 0:
            return Value
        User = 0
        for i in range(1, Value+1):
            User += UserCount(Floor-1, i)
        return User
    
T = int(input()) #테스트 케이스

for i in range(T):
    #구할려고 하는 층과 호
    k = int(input()) #층
    n = int(input()) #호

    print(UserCount(k, n))

문제에서 원하는 답을 도출하지만 백준에서 제시했던 조건 미달

시간제한 : 1초
메모리제한 : 128MB

4-1. 2차 풀이 (리스트에 담아 순차적으로 변경)

1. 0층 인원 수 List로 변수 설정
zero_User = list(range(1, n+1))

2. for문 중복 사용 (Floor + Room)
for x in range(k): #1층 값을 구하기 위해 0층을 확인해야하니 0층부터 시작
   for y in range(1, n): #모든 층에서 1호는 항상 1명이니 제외 (1층 2호부터 시작)
      zero_User[y] += zero_User[y-1]  

# (1층 2호) =  (0층 1호) + (0층 2호)
# (1층 3호) =  (0층 1호) + (0층 2호) + (0층 3호)  /// 대체 가능

5. 풀이 중 생각해야 했던 것

1. 필요한 0층의 List 목록을 받아와 계산을 할 때 중간부터 단순히 0호실 목록이 아닌 1호실 인원 수 목록과 중첩되어 있다는 것을 생각 필요 (sum(list(zero_User[:n+1])) 와 같은 문을 활용 시 문제 발생 )
[1,2,3,4,5] 0층 1~5호
[1,3,3,4,5] 1층 1호~2호 + 0층 3~5호

2. zero_User 리스트 내부에서 변경하지 말고 또 다른 List를 만들어 해당 리스트를 활용 했을 경우
추가적으로 작성 해야하는 코드가 많아지게 되며 분기 처리가 필요