[백준 알고리즘/python] 백준 2775번 부녀회장이 될테야, 파이썬

백준 알고리즘 2775번 부녀회장이 될테야, 파이썬

 

이번 문제는 백준 알고리즘의 2775번 부녀회장이 될테야. 문제이다.

파이썬으로 풀어보았다.

문제를 대충 설명하면 아파트의 거주 조건이 A층의 B호에 살려면 A-1층에서 B호까지 있는 사람들 수의 합만큼 데려와 살아야한다. 또, 0층의 i호에는 i명의 사람이 살고 있다.

 

이게 이렇게 보면 뭔말인가.. 싶겠지만 대충 표로 정리하면 한 눈에 보인다.

 

4층	1	6	21	56	126	252
3층	1	5	15	35	70	126
2층	1	4	10	20	35	56
1층	1	3	6	10	15	21
0층	1	2	3	4	5	6
	1호	2호	3호	4호	5호	6호

그러니까 예를 들어서, 빨갛게 표시 해 놓은 2층의 3호에 살려면 1층의 1호부터 3호까지있는 1 + 3 + 6 의 수 만큼 데려와 라는 소리다.

 

근데 이렇게 표로 만들어보니까 잘 보면 규칙이 있다.

바로 아래층의 전부를 더할 필요 없이, (바로 왼쪽 옆집 + 바로 아랫집)을 하면 수가 나온다.

 

위의 계산을 대충 점화식?으로 만들어보면 (h,n) = (h,n-1) + (h-1,n)이 된다. 이걸 알고 문제로 들어가자.

 

문제의 조건은 위에 다 나와있으니, 문제에 대한 내 생각이다.

#생각 1. 점화식을 구했으니, 이제 이차원 배열을 만들어서 그냥 처음부터 다 채워버리는게 좋을 것 같다.

#생각 2. 층 수는, 0층부터 14층까지 있고, 호수는 1호부터 14호까지있다. 왜냐면 문제 조건에 그렇게 나와있다.

#생각 3. 0층에 i호는 i명은 기본 조건, 각 층의 1호는 1명인것도 기본 조건 이 두개를 합쳐서 순차적으로 리스트를 채워나가면된다.

 

위처럼 생각을 하고 나는 코드를 짜 내려갔다.

 

 

 

 

 

내 코드이다.

lst = [[0 for j in range(14)] for i in range(15)]
for i in range(15):
    lst[i][0] = 1
for h in range(14):
    lst[0][h] = h+1
for i in range(1,15):
    for j in range(1,14):
        lst[i][j] = lst[i][j - 1] + lst[i - 1][j]

Test_case = int(input())
for i in range(Test_case):
    k = int(input())
    n = int(input())
    print(lst[k][n-1])

보면 알겠지만, 그냥 다 채우고나서 그 부분을 바로 받아오는 형식으로 코드를 썼다.

규칙을 찾는데 시간이 좀 걸렸지만, 푸는 방법은 되게 쉬웠다.

계차수열로 풀려고 들면 이거 머리 되게 아플 수도 있다.

이제 수학1 단계도 얼마 남지 않았다. 매일매일 조금씩 하다보면 언젠간 다 풀 날이 올거같다.

 

 

문제 출처

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

2775번: 부녀회장이 될테야