8095 : The Number of N-k-special Sets

풀이

1부터 N까지의 정수를 최대 한 번씩 사용하는데, 인접한 숫자를 사용하지 않고, k이상의 정수를 만드는 경우의 수를 구해야한다.

딱 문제가 저는 다이나믹이에요!!!! 라고 소리지르고 있다.

나는 두 가지 방법으로 풀었다.

아 그리고 답이 long long 범위마저 넘어가므로

Big Integer스러운 어떤 방법이나 언어를 잘 골라서 구현해야 한다.

방법1

dp[i][k] = 1~i를 사용해서 k를 만드는 경우의 수

i-1(인접하면 안 되니까 i-1)보다 작은 j들에 대해, dp[j][k-i]를 누적하여 세어주면 어렵지 않게 계산할 수 있다.

시간복잡도는 O(n*n*k)

방법2

방법1에서는 정확히 k를 만드는 경우의 수를 계산했다면, 이번에는

dp[i][k] = 1~i를 사용해서 k 이상을 만드는 경우의 수이다.

방법1에서 조금 발전시켜서 dp[i-1][j]를 누적해주자.

이 방법은 시간복잡도가 O(n*k)이다.

dp[i][j] = dp[i-1][j] + dp[i-2][j-i]

코드

n, K = list(map(int, input().split(' ')))
dp = [[0]*2600 for _ in range(101)]
dp[0][0] = dp[1][1] = dp[2][2] = 1
for i in range(3, n+1):
    for j in range(0, i-1):
        for k in range(0, 2600):
            if k-i >= 0:
                dp[i][k] = dp[i][k] + dp[j][k-i]
r = 0
for i in range(0, n+1):
    for j in range(K+1, 2600):
        r = r + dp[i][j]
print(r)
n, k = list(map(int, input().split(' ')))
dp = [[0]*402 for _ in range(101)]
dp[0][0] = dp[1][1] = 1
dp[1][0] = 2
for i in range(2, n+1):
    for j in range(k+2):
        dp[i][j] = dp[i-1][j] + dp[i-2][max(0, j-i)]
print(dp[n][k+1])

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-09-27 13:30

Read more posts by this author