[Python] 백준 알고리즘 문제풀이 :: 2775번

백준 알고리즘 문제풀이.

어렵지는 않은데, 규칙을 명확하게 이해하고 코드를 구현하기 좀 헷갈렸던 문제다.

문제

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

풀이

def summer(k, n):
    sum = 0
    if k == 0:
        sum += n
    elif k == 1:
        for i in range(1, n+1):
            sum += i
    else:
        for i in range(1, n+1):
            sum += i * summer(k-2, n-i+1)
    return sum
 
tc = int(input())
 
for i in range(tc):
    k = int(input())
    n = int(input())
    print(summer(k,n))

재귀함수를 이용해서 풀어주면 된다.

사실 테스트 케이스의 범위가 1<=k<=14, 1<=n<=14이기 때문에 문제 상에서 if k ==0 구간은 필요가 없다. 그냥 완벽한 함수를 만들기 위해 넣었다.

k == 1일 경우, n호의 가구원 수는 1부터 n까지의 합니다. for문을 1부터 n+1까지 돌려 sum에 각 i를 더해줬다.

k가 2 이상일 경우는 재귀함수를 쓰면 된다. 규칙이 얼추 알 것도 같은데, 명확하게 나오지 않아 그림처럼 직접 종이에 각 경우의 수를 모두 적어봤다.

어차피 결국은 자연수의 합의 조합이다. n에 따라 1부터 n까지의 자연수에 어떤 수를 곱해서 더해준다는 것을 찾았다.

그리고 그 곱해주는 수는 2단계 낮은 k를 집어넣은 함수의 결과값의 역순이라는 것을 알았다. 그래서 1부터 n까지의 각 i값에다가 summer(k-2, n-i+1)을 곱한 값을 sum 변수에 넣어줬다.

*처음에는 아래와 같이 작성했었다.

def summer(k, n):
    sum = 0
    if k == 1:
        for i in range(1, n+1):
            sum += i
        return sum
    else:
        for i in range(1, n+1):
            sum += summer(k-1, i)
        return sum
 
tc = int(input())
 
for i in range(tc):
    k = int(input())
    n = int(input())
    print(summer(k,n))

좀 더 직관적인 재귀함수. 바로 앞선 단계의 값을 1부터 n까지 모두 더해주는 거니깐. 그런데 시간초과가 났다. 답은 맞게 나오지만 다른 방법을 찾을 수 밖에 없었다. 그래서 수를 다 적어보고, 분해하면서 규칙을 찾아보니 또 다른 규칙이 보였다. 둘 다 재귀함수를 쓰는 건 맞는데 왜 시간이 차이가 많이 나는지는 잘 모르겠다.