[백준 7단계] 2775 부녀회장이 될테야 (중요)

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

문제 링크

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

2775번: 부녀회장이 될테야

🍒 문제 분석

0층에는 각 호수 값만큼을 가지고

1층 이상 부터는 , 한층 아래의 호수 가운데 1호부터 자기 자신의 호수까지의 합을 값으로 가진다.

따라서 1층 2호는 1 + 2 = 3 을 가지고

2층 3호는 1 + 3 + 6 = 10 을 가진다.

 

🥑 코드

• 이중 리스트 append 하는 풀이

T = int(input())
for _ in range(T):
    k = int(input())
    n = int(input())

    mylist = []                   # 아파트 구조
    for i in range(1,n+1):        # 0의 인원수를 채운다.
        mylist.append([])
        mylist[0].append(i)

    for j in range(1, k+1):              # 1층 부터 k층 까지; j
        mylist.append([])                # 층 생성
        for h in range(n):               # 1호 부터 n호 까지; h
            mylist[j].append(sum(mylist[j-1][:h+1]))   # j 층 h호 를 채워나간다.(단, 인덱스 0이 1호)
    
    print(mylist[k][n-1])

 

• 리스트 컴프리핸션 사용 풀이

T = int(input())
for _ in range(T):
    k = int(input())
    n = int(input())

    mylist = [[0]*(n+1) for _ in range(k+1)]     # k행 n열의 아파트 구조. 
    mylist[0] = [i for i in range(n+1)]          # 0행을 채워줍시다.

    for h in range(1,k+1):                       # 1행부터 k행 까지; h
        mylist[h] = [sum(mylist[h-1][:w+1]) for w in range(n+1)]      # 각 호수를 채워줬습니다; w
    
    print(mylist[k][n])

 

 

 

🍓 내 해결 과정

처음에는 재귀함수로 간단하게 풀었으나

역시나 시간 초과를 하여서, 리스트에 모든 값들을 저장하는 방법으로 방향을 선회 했다.

 

리스트 컴프리 핸션을 사용한 풀이를 기준으로 설명하자면,

1. 행을 k번 까지 가지고, 열을 n번 까지 가지는 아파트 구조를 만들었다. ( 0번 열은 안씀 )

2, 0번 행을 문제에서 주어진 조건을 가지고 채워넣고

3. 1번 행부터 k번 행 까지를 리스트 컴프리핸션으로 하나하나 채워주었다.

4. 각 행 (층) 의 호는, 한 행 아래의 열들의 합으로 이루어진다.

5. 이때 주의할 점은, 컴프리핸션을 쓸 때 0번 열을 비우고 하는게 안되므로 이를 고려해서 채워줄 것

(0번 열을 비우고 하는게 될 수도 있지만 굳이 알아보지 않았다. 어차피 아무 값이나 채워지면 되기 때문)

 

🍉 깨달은 점 및 정리

 

1. 문제 풀 때 팁을 하나 깨달았다.

https://callmescone.tistory.com/82

[ TIP ] 문제에서 1부터 시작할 때

 

2. 리스트 이중 구조 내에 요소를 추가할 때 알게된 내용

mylist = [[][]]*2
mylist[0].append(1)
# [[1][][1][]]  이렇게 됩니다. ( 얕은 복사 개념인 것 같음 )

mylist = [[]]
mylist.append([])
mylist.[0].append(1)
# [[1][]]
# 이중 리스트를 곱하기로 복제하면 안되고, append로 추가해야 이중리스트의 요소로 접근이 가능하다는걸 알게 됐네요 
# 보통 리스트 컴프레핸션 쓴다고 하네요

 

3. 리스트 컴프레핸션으로 다중 리스트 만들기

array = [[[] for _ in range(2)] for _ in range(2)]
# [[[], []], [[], []]]

 

4. 2번의 append로 리스트 안의 리스트 추가 하는 방식 보다,

컴프리핸션으로 미리 사전에 구조 만들어놓고 각 요소의 값 하나하나 바꾸는게 더 편하네요.

>>> mylist = [[] for _ in range(3)] 
>>> mylist 
[[], [], []]


>>> mylist[0] = [i for i in range(5)] 
>>> mylist[1] = [i**2 for i in range(3)]
>>> mylist[2] = [0]

>>> mylist
[[0, 1, 2, 3, 4], [0, 1, 4], [0]]