[BOJ] 백준 2775 부녀회장이 될테야 python

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

2775번: 부녀회장이 될테야

일단 나열해보고 관찰했다.

처음엔 막 1 + (1 + 2) + ... 이러면서 삽질을 좀 했는데,

보다 보니 한 칸 앞에 값과 한 칸 밑의 값을 더하면 현재의 값이 된다는 것을 발견하게 되었다.

원리(라고 하기엔 너무 거창하지만)를 한 번 알고 나니까 코드로 옮기는 것은 생각보다 수월했다.

 

count = int(input())

for _ in range(count):
	floors = int(input())
	rooms = int(input())
	result = [[1] for i in range(floors + 1)]
	result[0] = [i for i in range(rooms + 1)]
	for floor in range(1, floors + 1):
		for room in range(1, rooms + 1):
			if room == 1:
				result[floor].append(1)
			else:
				result[floor].append(result[floor - 1][room] + result[floor][room - 1])
	print(result[floors][rooms])