2775. [Python]부녀회장이 될테야

1. 문제

 

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

2775번: 부녀회장이 될테야

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 128MB
• 2차원 배열을 생성하여 접근

 

3. 파이썬 코드

 

T = int(input())
# 0층은 존재하지 않으므로 1~14호 까지는 직접 넣어주고 나머지 1층부터 14층까지는 0으로 이차원 배열을 생성해준다.
apt = [[1,2,3,4,5,6,7,8,9,10,11,12,13,14]] + [[0]*14 for _ in range(14)]

# 1층부터 15층까지 배열을 반복
for i in range(1,15):
# 1호실부터 14호실까지 반복문
    for j in range(14):
# 각 호실마다 들어가는 사람의 수는 "현재 층 -1"의 "현재 호수"까지 모든 사람들의 합이므로 3중 for문을 사용함.
        for k in range(j+1):
            apt[i][j] += apt[i-1][k]

# 미리 생성한 아파트 배열을 input값을 넣어주며 출력
for _ in range(T):
    k = int(input())
    n = int(input())
    print(apt[k][n-1])

 

4. 문제를 풀고난 후 생각

 

• 문제를 읽고 어떤식으로 구현을 해야하는지 생각하는데 시간이 소요됐다.
• Input 값이 들어오는 것마다 값들을 더해주는 것 보다는 수의 범위가 1~14까지로 제한되었기 때문에 이차원 배열을 생성하여 각 배열에 미리 값을 더해둔 후 그 값을 가져오는 식으로 구현하는 것이 좋을 것 같다는 생각이 들어 이차원 배열을 생성하였다.
• 숫자의 합을 더하거나 숫자들의 누적합등을 계산하는 문제는 미리 배열을 생성하여 계산 후 Input 값으로 조작하는 것이 들어오는 Input 값을 더해나가는 방식보다 시간 복잡도가 적게 소모되는 경우도 있으니 주의해서 문제를 풀자.
• 배열의 시작이 0부터 시작하는 것과 반복문을 구성할때 배열의 값을 제대로 불러오는지 등 배열 접근 방식에 대해서 잘 이해하는 것이 문제를 풀기에 필요한 기본 조건이였던 것 같다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 2차원 배열
• 배열의 개념
• 반복문