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

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

 

나의 답

N = int(input())

for _ in range (N):
    i = int(input())
    j = int(input())

    arr = [[0 for _ in range(j)] for _ in range(i+1)]


    for index in range(j):
        arr[0][index] = index+1
    
    
    
    for floor in range(1, i+1):
        for ho in range(j):
            for value in range(ho+1):                
                arr[floor][ho]+=arr[floor-1][value]
           
    print(arr[i][j-1], end =" ")

 

직접 그림을 그려보았다.

규칙을 찾고 싶었는데, 난 규칙을 찾을 수가.................없었다. 하하.

 

그래서 곧이 곧대로 구현을 했다.

우선 첫째 0층에 있는 값을 넣어둔 다음에, 그 값을 토대로 i,j 에 해당하는 값을 순서대로 구해서 넣었다.

 

그러고 난 담에, i,j-1에 해당하는 값 출력!

이 때, 2차원 배열을 깊은 복사를 해서 만들었어야 했는데, 얕은 복사를 잘못 해서 .. 시간을 꽤나 잡아먹은 것 같다.

 

 

배열을 만드는 게 시간이 더 오래걸릴 줄 알고

입력받은 값 중에서 젤 큰 값을 토대로 배열을 한번만 만드는 코드를 작성했는데, 시간이 전자가 더 짧게 나왔다..뭐지?

for문을 여러 번 돌리는 게 더 안좋은가보다..

N = int(input())

maxi = 0
maxj = 0

li = []

for _ in range (N):
    i = int(input())
    j = int(input())

    li.append((i,j))
    
    maxi = max(i,maxi)
    maxj = max(j, maxj)
    
for _ in range (N):

    arr = [[0 for _ in range(maxj)] for _ in range(maxi+1)]


    for index in range(maxj):
        arr[0][index] = index+1
    
    
    
    for floor in range(1, maxi+1):
        for ho in range(maxj):
            for value in range(ho+1):                
                arr[floor][ho]+=arr[floor-1][value]


for i in li:
    print(arr[i[0]][i[1]-1], end =" ")

가장 큰 값 추려내서 배열 한 번만 만든 코드 ..

 

다른사람풀이

https://velog.io/@beoldshoe/%EB%AC%B8%EC%A0%9C%ED%95%B4%EA%B2%B0-DP-BOJ2775-%EB%B6%80%EB%85%80%ED%9A%8C%EC%9E%A5%EC%9D%B4-%EB%90%A0%ED%85%8C%EC%95%BC-%EB%B8%8C%EB%A1%A0%EC%A6%88-1-Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC-qqol033u

[문제해결 - DP] BOJ2775 / 부녀회장이 될테야 / 브론즈 1 (Python, 파이썬)

 

이분 글을 참고하였다... DP를 사용하는 것!

저 규칙이 있었구나

for floor in range(1, maxi+1):
        for ho in range(maxj):
            arr[floor][ho] = arr[floor-1][ho]+arr[floor][ho-1]

합 구하는 부분을 이렇게 고쳐보았다.

 

시간이 매우 줄어들었다 ..  .. 짱 . . ~