Algorithm/Baekjoon Online Judge
[BOJ] 2775번
mirae.kwak
2022. 3. 12. 01:30
728x90
https://www.acmicpc.net/problem/2775
2775번: 부녀회장이 될테야
첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다
www.acmicpc.net
Python3
if __name__ == '__main__':
test = int(input())
for _ in range(test):
K = int(input())
N = int(input())
floor = [i for i in range(1, N+1)]
for k in range(K):
for n in range(1, N):
floor[n] += floor[n-1]
print(floor[N-1])
testcase의 개수를 받은 후 개수만큼 거주민을 구했다.
3층 | 1 | 5 | 15 | 35 | 70 |
2층 | 1 | 4 | 10 | 20 | 35 |
1층 | 1 | 3 | 6 | 10 | 15 |
0층 | 1 | 2 | 3 | 4 | 5 |
위와 같이 거주민이 구성되는데 이를 잘보면 2층 4호라고 하면 2층 3호의 거주민과 1층 4호의 거주민의 합으로 구할 수 있다. 2층 4호 거주민은 1층 1호부터 1층 4호까지의 거주민의 합인데 1층 3호까지 거주민의 합이 2층 3호에 있으므로 2층 3호 + 1층 4호를 통해 구할 수 있는 것이다.
따라서 코드에서는 0번 층을 기준으로 배열을 만들고 거주민의 수가 1인 1호를 제외하여 1층부터 K층까지 N호의 거주민의 수를 구한다. 여기서는 1차원 배열을 이용하고 있기 때문에 이 배열에서 k층의 n호의 거주민의 수를 구하려면 floor[n] += floor[n-1]로 가능하다. floor[n-1]에는 k-1층의 1호부터 n-1호까지 거주민의 수가 저장되어있고, floor[n]에는 k-1층의 n호 거주민의 수가 저장되어 있기 때문이다. 거주민의 수가 다 구해지면 마지막 열에 있는 거주민의 수를 출력한다.
728x90