AndroidTeacher

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

문제 설명

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

풀이 과정

이 문제에는 다음과 같은 규칙이 존재한다.

DP[1] = 1 ( 1 )

DP[2] = 2 ( 11 , 00 )

DP[3] = 3 ( 111, 100, 001)

DP[4] = 5 ( 1111, 1100, 1001, 1100, 0000 )

위 결과를 보면 알 수 있듯이 DP[n]은 DP[n-1] + DP[n-2] 의 형식으로 쌓아가는 것을 볼 수 있다.

1은 단독으로 쓰일 수 있지만 0은 단독으로 쓰일 수 없기 때문에

현재 결과에 '1' 만을 붙여 다음값을 만들 수 있지만

'0'만을 붙여 다음값을 만들 수 없으므로 '00'을 붙여 다음 값을 만들게 된다.

하지만 '00'은 길이가 2 이므로 현재값에 붙이면 길이가 초과하게 되므로 이전값에 붙여주어야 한다.

예를 들어,

DP[4]의 경우에는

DP[3]의 각각의 값에 1을 붙인 것과

DP[2]의 각각의 값에 00을 붙인 것과 같다.

이 특징을 살려 코드를 구현하면 다음과 같다.

다만, 문제의 n이 최대 1,000,000 이므로 계산 중간 int의 범위를 벗어나는 경우가 생기므로

맨 마지막 결과가 아닌 중간중간 %15746을 해야한다.

n = int(input())

dp = [0]*(n+1)
dp[1] = 1
dp[2] = 2

for i in range(3, n+1):
    dp[i] = (dp[i-1] + dp[i-2]) % 15746

print(dp[n])

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

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

문제 설명

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
    1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
    w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
    w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

이러한 재귀함수 w를 수행시간이 짧아지도록 구현하는 문제이다.

풀이 과정

문제에서 주어진 재귀함수의 수행시간이 오래걸리는 이유는 매번 값을 계산하기 때문이다.

한 번 계산된 값도 다음에 다시 계산이 된다.

그래서 매번 값을 계산하도록 하는 형식이 아닌 한 번 계산된 값은 저장하도록 하면 된다.

그래서 DP를 이용하자.

문제에서 주어진 조건문은 그대로 구현을 해주면 된다.

단지, 계산된 값만 3차원 DP배열에 저장을 해줌으로써 재 계산을 할 필요가 없도록 하면 된다.

import sys
dp = [[[0]*21 for _ in range(21)] for _ in range(21)]

def w(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    if a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)

    if dp[a][b][c]:
        return dp[a][b][c]

    if a < b < c:
        dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
        return dp[a][b][c]

    dp[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
    return dp[a][b][c]

while True:
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    if a == -1 and b == -1 and c == -1:
        break
    ans = w(a, b, c)
    print("w(%d, %d, %d) = %d" %(a, b, c, ans))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

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

문제 설명

격자 맵과 한 지점이 주어졌을 때,

시작점 부터 그 지점을 거쳐 종료점까지 만들 수 있는 경로의 개수를 구하는 문제이다.

풀이 과정

경우의 수와 DP를 활용하는 문제이다.

초등학교 때 길 찾기 경우의 수를 배울 때 이러한 방법을 사용했을 것이다.

위 표처럼 가장 첫 칸과 첫 행을 1로 채우고

다음칸부터 왼쪽과 위쪽칸의 수를 더해 칸을 채워 나가는 방식이다.

이 규칙에, 문제에서 지정한 칸을 반드시 거치는 경로의 수를 구하는 문제이다.

예를 들어, 2행 2열 칸을 반드시 거쳐 지나가야 한다고 하자.

그럼 먼저, 2행 2열 칸 까지 가는데의 경우의 수를 구한 후

그 칸을 시작점으로 생각하여 도착점 까지의 경우의 수를 처음부터 구한다는 생각으로 구한 후

두 수를 곱해주면 될 것이다.

그래서 구한 2와 3을 곱하면 6이 되므로

2행 2열 칸을 반드시 거치는 경로의 수는 총 6이 된다.

이를 코드로 옮기면 다음과 같다.

n, m, k = map(int, input().split())
dp = [[0] * m for _ in range(n)]

if k == 0:
    for i in range(n):
        for j in range(m):
            if i == 0 or j == 0:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    print(dp[n - 1][m - 1])

else:
    x = (k - 1) // m
    y = (k - 1) % m

    for i in range(x + 1):
        for j in range(y + 1):
            if i == 0 or j == 0:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    for i in range(x, n):
        for j in range(y, m):
            if i == x and j == y:
                continue
            if i == x:
                dp[i][j] = 1
            elif j == y:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    print(dp[x][y] * dp[n - 1][m - 1])

위 코드보다 조금 짧고 간결하게 구현을 하고 싶다면,

두 개로 나눈 for문 대신

(x, y)칸과 (n-x, m-y)칸의 값을 곱하는 방식으로 구현해도 된다.

( 어차피 (x, y)칸 부터 새로 시작하는 것과 같기 때문이다 )

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

문제 설명

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

상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

위의 그림의 경우에 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 가장 높은 점수를 가지는 두 스티커 (100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

풀이 과정

스티커를 떼면 뗀 칸의 왼쪽, 오른쪽, 위, 아래 칸의 스티커도 같이 떼어지기 때문에

어떤 스티커를 선택하느냐에 따라 다음칸에 선택할 수 있는 스티커가 한정된다.

따라서 DP(다이나믹 프로그래밍)을 통해 최대값을 누적해가며 어떤 스티커를 뗄 지를 선택해야 한다.

위의 표모양과 같은 스티커가 있을 때,

제일 오른쪽 위의 스티커(graph[0][4])를 뗄 수 있는 상황은

이전에 graph[1][3]을 선택하거나 graph[1][2]를 선택했을 때 이다.

graph[0][3]을 선택하면 바로 오른쪽인 graph[0][4]도 같이 떼어지기 때문에 선택할 수 없기 때문이다.

그래서 graph[1][3]과 graph[1][2]에 누적된 값 중 최댓값을 선택하여 graph[0][4]를 더해주면

graph[0][4]를 선택했을 때의 최대값을 구할 수 있게 된다.

(여기서 graph[0][2]를 고려하지 않는 이유는 graph[1][3]의 누적값에 graph[0][2]선택값도 포함되어 있기 때문이다.)

이를 코드로 나타내면 다음과 같다.

t = int(input())

for i in range(t): #전체 테스트 횟수
    col = int(input())
    graph=[]
    for j in range(2): #row은 항상 2줄
        graph.append(list(map(int, input().split())))

    if col == 1:
        print(max(graph[0][0], graph[1][0]))
        continue

    graph[0][1] += graph[1][0]
    graph[1][1] += graph[0][0]

    for k in range(2, col):
        graph[0][k] += max(graph[1][k-1], graph[1][k-2])
        graph[1][k] += max(graph[0][k-1], graph[0][k-2])

    print(max(graph[0][col-1], graph[1][col-1]))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

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

문제 설명

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

풀이 과정

먼저, 벽을 체울 수 있는 경우의 수를 구해보자.

벽의 가로길이가 홀수라면 벽을 가득 체울 수 없다.

예를 들어, N = 1 이라면 아래 한 칸이 남기 때문에 벽을 체울 수 없다. (타일은 2x1과 1x2만 존재하기 때문에)

N = 2 일때는 다음과 같이 3가지 경우의 수가 존재한다.

N = 4 일 때는 가로를 반으로 나눠 N = 2가 2개 있다고 생각할 수 있다.

그래서 앞의 3가지 x 뒤의 3가지 = 9 가지 경우의 수가 나타날 수 있다.

여기에 다음과 같은 모양의 벽 2가지를 더 추가해야 한다.

그래서 총 11가지 경우의 수가 존재한다.

이 때, 위의 벽의 모양처럼 더 추가해야 하는 벽은 

N이 2가 커질수록 2가지씩 더 늘어난다.

(직접 그림을 그려보면 더 이해하기 쉬울 것이다.)

이를 활용하여 N을 끝 지점으로 가져가보자.

끝점으로부터 2칸을 채워야 하는 경우는 다음과 같이 3가지 경우가 존재한다.

이 경우의 수는 3 x DP[N-2]가 될 것이다.

여기에, 위의 [그림3]에서 그린 것 처럼, 가로가 N일 때만 가능한 경우의 수가 2가지 존재하기 때문에 2를 추가한다.

그럼, DP[N] = DP[N-2] * 3 + 2 라는 점화식을 세울 수 있다.

하지만, 여기서 한 가지 더 고려해야 할 점이 있다.

끝점으로부터 4칸 이상이 남았을 경우에는 현재 상태에 [그림3]처럼 그 타일만의 고유 모양 2가지를 추가할 수 있기 때문에 2부터 N-2 이전까지의 각 칸에 +2를 해주어야 한다.

따라서, 이들을 총 고려한 점화식은 다음과 같다.

DP[N] = DP[N-2]* 3 + 2부터 N까지의 DP값에 x2 

이를 파이썬으로 나타낸 코드는 다음과 같다.

n = int(input())

dp = [0]*(n+1)

if n % 2 != 0:
    print(0)
else:
    dp[2] = 3
    for i in range(4, n+1, 2):
        dp[i] = dp[i-2] * 3 + 2
        for j in range(2, i-2, 2):
            dp[i] += dp[j] * 2

    print(dp[n])

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

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

문제 설명

자세한 문제 설명은 위 링크를 참조해 주세요

1번부터 N번까지의 도시가 있고, 어느 한 도시를 출발하여 모든 도시를 찍고 다시 출발지점으로 돌아오는데 드는 최소 비용을 구하는 문제이다.

풀이 과정

이 문제는 비트마스킹 + DP + DFS 를 모두 활용하는 문제로 난이도가 있는 문제이다.

각 도시를 방문했는지의 여부는 비트마스킹( 0001, 0002 ... 1111 )을 활용하고

현재 도시에서의 최소비용은 DP를 활용하고

도시를 방문하는 것은 DFS를 활용한다.

① 먼저, 출발도시를 정해야 한다.

나는 0번 도시를 출발지점으로 정했는데, 어느 도시를 출발지점으로 정하든지 상관이 없다.

문제에서, 그래프는 순환경로(싸이클)를 이루기 때문에

만약, 1 -> 0 -> 3 -> 2 -> 1 경로가 최소 비용 경로라면

0 -> 3 -> 2 -> 1 -> 0 도 최소 비용 경로가 되기 때문이다.

즉, 출발점 1 에서 최소 비용 경로가 존재할 때, 0에서도 같은 경로가 반드시 존재하게 된다.

② 거친 도시를 비트마스킹으로 표시한다.

visited라는 변수에 2진수로 거친 도시를 표시하였다.

visited에 다음과 같이 값을 할당한다.

0001(2) = 1 이라면 => 0번 도시만을 거침

0011(2) = 3 이라면 => 0, 1 번 도시를 거침

1111(2) = 15 이라면 => 0, 1, 2, 3 번 도시를 거침

이렇게 어느 도시들을 거쳤는지 거치지 않았는지를 비트마스크로 표시하였다.

③ dp에는 현재 도시에서 남은 도시들을 거쳐 다시 출발점으로 돌아오는 비용이 저장된다.

dp[cur][visit] = 현재 cur도시이며 방문현황은 visit과 같고, 아직 방문하지 않은 도시들을 모두 거쳐 다시 시작점으로 돌아가는데 드는 최소 비용

점화식이 잘 이해가 가지 않는다면,

뒤에서 부터 생각하면 좀 더 이해하기 쉬울 것이다.

dp[next][nextvisit]이 next도시에서 남은 도시를 거쳐 시작점으로 돌아가는 최소비용이기 때문에

dp[cur][visit]은 dp[next][nextvisit]보다 graph[cur][next]만큼의 비용이 더 들 것이다.

즉, 다음 지점의 dp보다 다음 지점으로 가는데에 드는 비용만큼 더 들게 되는 것이다.

예를 들어, dp[0][0011(2)] = dp[0][3]은 현재 0번 도시이며, 0, 1번 도시를 방문하였고, 2, 3을 방문한 후 다시 시작점으로 돌아갈 때의 최소 비용이며

dp[2][0111(2)] = dp[2][7]은 현재 2번 도시이며 0,1,2 번 도시를 방문하였으며, 3을 방문한 후 다시 시작점으로 돌아갈 때의 최소비용이다.

즉, dp[0][0011] = dp[2][0111] + graph[0][2]이 되는 것이다.

이를 점화식으로 나타내면 다음과 같다.

dp[cur][visited] = min(dp[cur][visited], dp[next][visited | (1 << next)] + graph[cur][next])

④ DFS를 통해 DP값을 갱신시켜 준다.

dp[next][visited | (1<<next)] 부분을

dfs(next, visited | (1<<next) ) 를 통해 재귀함수를 돌리며 DP값을 갱신시켜준다.

위 방식을 파이썬으로 나타낸 코드는 다음과 같다.

n = int(input())

INF = int(1e9)
dp = [[INF] * (1 << n) for _ in range(n)]


def dfs(x, visited):
    if visited == (1 << n) - 1:     # 모든 도시를 방문했다면
        if graph[x][0]:             # 출발점으로 가는 경로가 있을 때
            return graph[x][0]
        else:                       # 출발점으로 가는 경로가 없을 때
            return INF

    if dp[x][visited] != INF:       # 이미 최소비용이 계산되어 있다면
        return dp[x][visited]

    for i in range(1, n):           # 모든 도시를 탐방
        if not graph[x][i]:         # 가는 경로가 없다면 skip
            continue
        if visited & (1 << i):      # 이미 방문한 도시라면 skip
            continue

        # 점화식 부분(위 설명 참고)
        dp[x][visited] = min(dp[x][visited], dfs(i, visited | (1 << i)) + graph[x][i])
    return dp[x][visited]


graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))

print(dfs(0, 1))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

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

문제 설명

이 문제는 아주 평범한 배낭에 관한 문제이다.

흔히, 냅색(Knapsack) 알고리즘이라고 불리는 문제이다.

배낭의 용량이 정해져 있을 때, 최대한의 가치를 가지도록 배낭을 싸야 한다.

주어진 물건들의 용량과 가치를 고려하여 주워담을지 말지 정하는 문제이다.

풀이 과정

먼저, 내 배낭이 버틸 수 있는 용량이 7이라고 하자. K=7 이다.

그리고 물건이 4개 있는데 (N = 4), 각각의 무게와 가치가 다음 표와 같다고 하자.

첫 번째 물건부터 살펴보면 무게가 6인데, 내 배낭은 현재 0 무게이므로 담을 수 있다.

두 번째 물건을 살펴보면, 무게가 4이다. 첫 번째 물건을 담았으면 4+6 > 7 (배낭의 최대) 이므로 담을 수 없고

첫 번째를 버리던가, 두 번째를 담지않던가 선택을 해야한다.

지금 당장은 첫 번째를 가져가는게 맞지만, 후에는 어떤 것을 담는것이 더 가치있는지 모른다.

그래서, 더 가치있는 것을 판별해줄 알고리즘을 짜야 한다.

그럼, 이렇게 생각해보자.

N * K 의 2차원 배열 d[n][k]를 만들어 각각의 물건을 선택할 때 마다 최대 가치를 판별해줄 수 있도록 하자.

d[n][k]는 N번째 물건 까지 살펴보았을 때, 무게가 K인 배낭의 최대 가치 이다.

물건을 배낭에 담을 때,

① 현재 배낭의 허용 무게보다 넣을 물건의 무게가 더 크다면 넣지 않는다.

② 그렇지 않다면, 다음 중 더 나은 가치를 선택하여 넣는다

    2-1) 현재 넣을 물건의 무게만큼 배낭에서 뺀다. 그리고 현재 물건을 넣는다.

    2-2) 현재 물건을 넣지않고 이전 배낭 그대로 가지고 간다.

위 과정을 식으로 나타내면 다음과 같다.

현재 담을 물건의 인덱스를 i, 현재 가방 허용 용량이 j, 현재 담을 물건의 무게를 weight, 가치 value라고 할 때,

① j < weight : d[i][j] = d[i-1][j]

② d[i][j] = max( d[i-1][ j-weight ]+value ), d[i-1][j] )

2-1)의 과정에서, 현재 넣을 물건의 무게만큼 배낭에서 뺀다고 한 부분에 이런 의문점이 들 수 있다.

현재 넣을 무게와 똑같은 무게의 물건이 없으면, 어떻게 빼는가? 물건이기 때문에 쪼개지 못하는데?

하지만, 현재 넣을 물건의 무게만큼 뺀 배낭에는,

그 무게의 배낭이 가지는 최대 가치가 저장되어 있다. 그래서 상관없다.

예를 들어, 현재 무게 7의 배낭에 무게 4 짜리 물건을 넣으려고 한다면

무게 4를 배낭에서 뺀 후에 그 때의 배낭가치에 현재 물건을 넣었을 때의 가치를 더해주어야 하는데,

내 배낭속에는 무게 4짜리 물건이 없고, 무게 3짜리밖에 없다고 하자.

하지만 d[n][3]에는 이미 무게 3인 배낭이 가지는 최대 가치가 저장되어 있고

d[n][4]에는 무게 4인 배낭이 가지는 최대 가치가 저장되어 있기 때문에 상관 없는 것이다.

직접 표를 그려보면 더 이해하기 쉬울 것이다.

이를 이용한 최종 코드는 다음과 같다.

n, k = map(int, input().split())

thing = [[0,0]]
d = [[0]*(k+1) for _ in range(n+1)]

for i in range(n):
    thing.append(list(map(int, input().split())))

for i in range(1, n+1):
    for j in range(1, k+1):
        w = thing[i][0]
        v = thing[i][1]

        if j < w:
            d[i][j] = d[i-1][j]
        else:
            d[i][j] = max(d[i-1][j], d[i-1][j-w]+v)

print(d[n][k])

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/2225

문제 설명

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우).

또한 한 개의 수를 여러 번 쓸 수도 있다.

풀이 과정

이 문제는 코드는 간단해보일지 몰라도, 아이디어를 떠올리는 과정이 굉장히 까다로웠다.

나는 DP와 순열과조합의 개념을 조합하여 아이디어를 떠올렸다.

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 d[N][K]에 저장한다고 하자.

N = 2, K = 1 일 경우 0부터 2까지의 정수 1개를 더해 합이 2이 되는 경우의 수이므로,

만들 수 있는 경우의 수는 (2) 한가지 밖에 없을 것이다. 즉, d[2][1] = 1

N = 2, K = 2 일 경우 0부터 2까지의 정수 2개를 더해 합이 2이 되는 경우의 수이므로,

(2+0), (0+2), (1+1) 이렇게 세 가지가 존재한다. d[2][2] = 3

N = 2, K = 3 일 경우 0부터 2까지의 정수 3개를 더해 합이 2이 되는 경우의 수이므로,

(0+0+2), (0+2+0), (2+0+0), (0+1+1), (1+0+1), (1+1+0) 이렇게 여섯가지가 존재한다. d[2][3] = 6

그럼 이제 규칙을 한번 살펴보자.

K=2인 경우와 K=3인 경우를 비교해 보자.

K=3인 경우는 K=2인 경우에 정수 1개를 더 추가한 것이다. 합은 그대로인 상태로.

즉, 0부터 2까지의 정수 3개를 더해 합이 2이 되는 경우의 수는,

0부터 2까지의 정수 2개를 더해 합이 2-A이 되는 경우의 수에, 정수 A를 더 추가하여 나타내는 것이다.

식으로 나타내 보면, d[2][3] = d[2][2] + d[1][2] + d[0][2] 와 같이 나타낼 수 있다.

                                                        0추가       1추가      2추가

즉, d[n][k] = d[0][k-1] + d[1][k-1] + d[2][k-1] + ... d[n][k-1] 과 같이 나타낼 수 있다.

이를 코드로 나타내면 다음과 같다.

for i in range(1, n+1):
    for j in range(1, k+1):
        for k in range(i):
            d[i][j] += d[k][j-1]

하지만, 이러한 형식으로 3중 for문을 돌게되면, 시간복잡도가 O(KN^2)이 된다.

즉 거의 O(N^3)에 수렴하게 된다.

그래서 다음과 같은 아이디어를 떠올릴 수 있다.

d[n][k] = d[0][k-1] + d[1][k-1] +  ...  + d[n-1][k-1] + d[n][k-1] 에서

d[n-1][k] = d[0][k-1] + d[1][k-1] + ... + d[n-1][k-1] 이므로, 파란부분을 치환하면

d[n][k] = d[n-1][k] + d[n][k-1] 과 같이 나타낼 수 있다.

코드로 나타내면 다음과 같다.

n, k = map(int, input().split())

d = [[0]*(k+1) for _ in range(n+1)]

for i in range(k+1):
    d[0][i] = 1

for i in range(1, n+1):
    for j in range(1, k+1):
        d[i][j] = d[i][j-1] + d[i-1][j]
        d[i][j] %= 1000000000

print(d[n][k])

d[0][i] 는 0을 나타낼 수 있는 경우의 수는 무조건 1가지 이기 때문에 1로 설정을 해주었다.

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !