[BOJ #1010] 다리놓기(Python)

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

잠이안와서 알고리즘을 풀기로했다. 최근에 책으로 DP풀이에 관한 부분을 읽어서인지 문제를 보자마자 바텀업 방식으로 풀어야겠다고 생각이 들었다. 다리가 N, M으로 있기 때문에 2차원 배열을 써야겠다고 생각

근데 내가 점화식을 잘 못만든다는걸 깜빡하고 풀기시작해서 새벽에 그림판에 그려가면서 겨우겨우 점화식을 만들었다..

gpt에게 부탁해서 시각적 개선을했다

 

규칙을 찾아낸 다음엔 DP를 초기화하고 코드로 작성하기까지는 수월했다.

풀이

tc = int(input())
for _ in range(tc):
    N, M = map(int, input().split())
    arr = [[0] * (M+1) for _ in range(N+1)]

    for i in range(N+1):
        for j in range(M+1):
            if i == 0:
                arr[i][j] = 0
            elif i == 1:
                arr[i][j] = j
            elif i == j:
                arr[i][j] = 1
            else:
                arr[i][j] = sum(arr[i-1][1:j])

    print(arr[N][M])

 

정답이었지만 코드개선 + 더 나은 풀이가 있을거라는 생각에 서치를 했는데

위 풀이는 sum() 연산이 반복적으로 수행되어 M이 커질수록 시간복잡도가 폭발적으로 증가한다고 한다.

이 문제는 누적합을 이용하여 해결이 가능하고 다음과 같이 코드를 최적화 했다.

개선 코드

tc = int(input())
for _ in range(tc):
    N, M = map(int, input().split())
    arr = [[0] * (M+1) for _ in range(N+1)]

    for j in range(M+1):
        arr[1][j] = j
        
    for i in range(2, N+1):
        prev = [0] * (M+1)
        for j in range(M+1):
            prev[j] = prev[j-1] + arr[i-1][j]
        for j in range(i, M+1):
            arr[i][j] = prev[j-1]

    print(arr[N][M])

 

O(N × M) vs O(N × M²) 성장 속도 비교

 

그래프로 보면 M값에 따라 차이가 매우 컸던 것을 개선한걸 눈으로 확인할 수 있다.

아마 테스트케이스 범위가 큰 문제였다면 틀렸을 것 같다.

문제와 궁금증 모두해결 끝.