#29 동적 계획법 4 - 경우의 수
동적 계획법을 적용하여 경우의 수를 구하는 문제를 알아본다.
1. RGB거리 2(https://www.acmicpc.net/problem/17404)
n 개의 집이 직선상에 번호순서대로 있고 각 집을 빨강, 초록, 파랑의 색으로 칠하기 위해 필요한 비용이 주어졌을 때, 인접한 집 끼리는 색이 같지 않도록 칠하는 경우의 수를 구하는 문제. 단, 1번 집과 n번 집의 색도 서로 달라야한다.
동적계획법을 적용한 완전탐색 문제이다. 집을 순차적으로 방문하여 이전 집과 겹치지 않는 색상 중 어느 색상으로 칠해야 비용을 최소화 할 수 있는지 재귀적으로 구해나가면 간단하게 해결할 수 있다. 주의할 점은 마지막 집이 첫 번째 집과도 색이 겹쳐선 안된다는 조건이 있기에 첫 번째 집의 색상을 저장해두고 마지막 집의 색상을 정할 때 반영해야한다는 것이다. 문제를 해결한 코드는 다음과 같다.
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 10**9
def sol17404():
# 집의 갯수
n = int(input())
# 각 집을 빨강, 초록, 파랑으로 칠하기 위한 비용
cost = [list(map(int, input().split())) for _ in range(n)]
# dp[i][j] 는 i 번째 집의 색이 j 일 때 최소 누적비용
dp = [[0] * 3 for _ in range(n)]
# 완전탐색 함수 - 이전집의 색과 현재 집의 번호를 인자로 받는다
def dfs(pre, cur):
# 첫 번째 집의 색
nonlocal f
# 마지막 집까지 모두 칠했다면 더이상 비용은 들지않는다.
if cur == n:
return 0
# 현재 집을 이전 집과(마지막 집의 경우 첫 번째 집과도) 색이 겹치지 않도록 칠할 때
# 그 비용을 최소화시킬 수 있는 경우를 구한다
res = INF
for c in range(3):
if (c == pre) or (cur == n-1 and c == f):
continue
if not dp[cur][c]:
dp[cur][c] = dfs(c, cur+1) + cost[cur][c]
res = min(res, dp[cur][c])
# 현재 집의 색에 따른 총 비용 중 최솟값
return res
# 첫 번째 집의 색에 따라 세 번 탐색하여 최소비용을 구함
answer = INF
for f in range(3):
dp = [[0] * 3 for _ in range(n)]
answer = min(answer, dfs(f, 1)+cost[0][f])
# 최소비용 반환
return answer
2. 색상환(https://www.acmicpc.net/problem/2482)
n 개의 색상이 있는 색상환에서 k개의 색을 서로 인접하지 않도록 고르는 경우의 수를 구하는 문제. 동적계획법을 활용한 풀이와 조합을 활용한 풀이 두 가지 방법이 있다.
1) 동적 계획법을 활용한 풀이
양 끝이 인접해있는 원형임을 일단 생각하지 않고 선형의 리스트에서 인접하지 않도록 k개를 뽑는 경우를 생각해보자.
dp[i][j] 가 i 번째 까지의 색상리스트에서 j 개의 색을 인접하지 않도록 뽑는 경우의 수라고 할 때, 다음과 같은 점화식이 성립한다.
dp[i][j] = dp[i-1][j] + dp[i-2][j-1]위와 같은 점화식이 성립하는 이유는 현재 보고있는 i 번째 색을 선택할지, 선택하지 않을지 여부에 따라 두 가지 경우의 수로 나뉘기 때문이다.
① i 번째 색을 선택할 경우 이전의 색은 선택될 수 없다. 또한 이번 색을 선택함으로서 j개의 선택이 완료되어야
하기 때문에 그 전까지 j-1 개의 선택이 완료된 상태여야 한다. (dp[i-2][j-1])
② i 번째 색을 선택하지 않을 경우 이전의 색도 선택될 수 있으며, 이번에 색을 선택하지 않기 때문에 그 전까지
이미 j 개의 선택이 모두 완료된 상태여야 한다. (dp[i-1][j-2])
이제 첫 번째 색과 마지막 색이 인접해서는 안된다는 조건을 처리해야한다.
① 마지막 색을 선택할 경우, 자기 자신과 좌우로 두 개의 인접한 색을 제외한 범위에서
k-1개의 색을 선택한 상태여야 한다. (dp[n-3][k-1])
② 마지막 색을 선택하지 않을 경우, 그 전까지 j-1 개의 선택을 완료한 상태여야 한다. (dp[n-1][k])
이를 구현한 코드는 다음과 같다.
import sys
input = sys.stdin.read
mod = 1000000003
def sol2482():
# 색상의 갯수와 골라야할 색상의 수
n, k = map(int, input().split())
# dp[i][j] 는 i번까지의 색상리스트중 j개를 고르는 경우의 수
dp = [[0] * (k + 1) for _ in range(n + 1)]
# 0개를 고르는 경우는 항상 1이며 1개를 고르는 경우는 항상 색상의 갯수와 같다.
for i in range(n + 1):
dp[i][0] = 1
dp[i][1] = i
# 점화식에 따라 dp를 채워나간다
for i in range(2, n + 1):
for j in range(2, k + 1):
dp[i][j] = (dp[i - 2][j - 1] + dp[i - 1][j]) % mod
# 양 끝이 인접할 경우를 고려하여 경우의 수를 구하여 반환한다
return (dp[n - 3][k - 1] + dp[n - 1][k]) % mod
2) 조합을 활용한 풀이
n 개의 색상에서 인접하지 않도록 색상을 최대한 많이 고르는 경우는 한칸씩 띄어가며 선택하는 것이다. 즉, 고르려는 색상의 갯수 k 가 n의 절반을 넘을 경우 인접하지 않도록 색상을 고르는 것은 불가능하다.
if k > n//2:
return 0k가 n의 절반 이하라면 경우의 수는 한 개이상 존재한다. 이 때, 그 경우의 수를 다음과 같이 생각해볼 수 있다.
n개의 색상칸에 선택할 색상 k 개를 제외한 선택하지 않을 n-k 개의 색을 먼저 나열해놨다고 할 때(녹색칸), 위 그림과 같이 선택하지 않은 칸을 사이에 두고 슬롯이 n-k+1 개 생긴다.(하얀칸) 선택받은 k개의 색상을 슬롯에 넣는 경우의 수를 생각하면 combination(n-k+1, k) 가 된다. 그런데 이 표는 편의상 리스트형태로 표현했을 뿐 환형이기 때문에 만약 k개의 슬롯을 선택했을 때 양 끝이 모두 선택된다면 양 끝이 맞닿는 문제가 발생한다. 그 경우의 수는 양 끝의 슬롯을 이미 선택했다고 가정하고 남은 n-k-1 개의 슬롯에서 k-2 개의 슬롯을 고르는 경우의 수, 즉 combination(n-k-1, k-2) 가 된다.
둘의 차를 구하면 k개의 색상이 서로 인접하지 않도록 선택하는 모든 경우의 수를 구할 수 있다. 이를 구현한 코드는 다음과 같다.
import sys
input = sys.stdin.read
mod = 1000000003
def sol2482():
# 색상의 총 수 n, 골라야할 색상의 수 k
n, k = map(int, input().split())
# 골라야할 색상의 수가 총 색상 수의 절반을 넘기면 인접하지 않도록 고르는것은 불가능
if k > n//2:
return 0
# 1개의 색을 고르는 경우의 수는 총 색상 수와 같음
if k == 1:
return n
# n-k개의 고르지 않은 수의 사이에 존재하는 슬롯 n-k+1 개에서 k개의 슬롯을 골라 수를 삽입
# 양 끝 슬롯을 함께고르는 경우를 배제하기 위해 양 끝 슬롯을 제외한 n-k-1 개의 슬롯에서
# k-2개의 슬롯을 고르는 경우의 수를 감산
return (bc(n-k+1, k) - bc(n-k-1, k-2)) % mod
# 이항계수를 반환하는 함수
def bc(a, b):
b = min(b, a-b)
u, v = 1, 1
for i in range(b):
u *= (a - i)
v *= (1 + i)
return u//v이러한 풀이는 실전에서 떠올릴 수 있다면 좋겠지만 너무 몰입하다간 문제해결에 과하게 시간을 낭비할 수 있기 때문에 조금 시도해보다가 답이 보이지 않는다면 과감하게 포기하고 다른 해결책을 모색해보는 것도 좋을 것 같다.