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

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

2775번: 부녀회장이 될테야

알고리즘 분류 : 수학, 구현

 

---

문제의 설명을 그림으로 나타내면 다음과 같다.

1층의 2호실에 있는 사람의 수는 0층의 1, 2호실 사람들의 수와 같다.

2층 3호실에 있는 사람의 수는 1층의 1, 2, 3호실 사람들의 수와 같다.

 

0층의 인원들을 리스트로 나타내면 다음과 같을 것이다.

lst = [1, 2, 3, 4]

몇층이 되던간에 lst[0] = 1로 동일한 반면, 다음 층의 lst[1]은  이전층의 lst[1] + lst[0]의 값과 같다.

 

 

그렇게 구한 다음층의 lst[1]의 값에 이전층의 lst[2]값을 더하면 다음층의 lst[2]값을 구할 수 있다.

변수 height를 층 수로,

변수 weight를 호 수로 나타냈을때 다음과 같은 방법으로 코드를 구현했다.

 

T = int(input())

for i in range(T):
    height = int(input())    #층
    weight = int(input())    #호
    lst = [j for j in range(1, weight+1)] # 0층
    
    for k in range(1, height+1):    #1층~height층
        for l in range(1, weight):
            lst[l] += lst[l-1]
    print(lst[weight-1])

리스트 lst는 1~입력받은 호수 weight까지의 값을 리스트로 담는다.

2층 3호를 입력했다면 lst = [1, 2, 3]이 될 것이다. 이는 위의 그림과 같이 0층일때의 인원 수를 간단하게 나타낸 것이다.

 

k = 1 (1층)

lst[1] = lst[1] + lst[0]

lst[2] = lst[2] + lst[1]

 

k = 2 (2층)

lst[1] = lst[1] + lst[0]

lst[2] = lst[2] + lst[1]

 

바로 앞 인덱스의 값만 더해주는 것만 반복하면 된다.

 

 

T = int(input())

for i in range(T):
    height = int(input())    
    weight = int(input())    
    lst = [j for j in range(1, weight+1)] # 0층
    print(lst)   #수정
    for k in range(1, height+1):    #1층~height층
        for l in range(1, weight):
            lst[l] += lst[l-1]
        print(lst)   #수정

코드를 이렇게 바꿔주면 0층에서 입력한 층 수까지의 모든 값을 확인할 수 있다.

height = 3
weight = 4
>>
0층 : [1, 2, 3, 4]
1층 : [1, 3, 6, 10]
2층 : [1, 4, 10, 20]
3층 : [1, 5, 15, 35]

여기서는 3층의 35가 3층 4호실 위치의 거주민 수가 되므로 lst[weight-1]의 값으로 뽑아낼 수 있다.