문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰인 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총합을 계산하시오. 예를 들어, C1, C2, C3, C4가 연속적인 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 각각 40, 30, 30, 50 이라고 하자. 이 파일들을 합치는 과정에서, 먼저 C2와 C3를 합쳐서 임시파일 X1을 만든다. 이때 비용 60이 필요하다. 그다음으로 C1과 X1을 합쳐 임시파일 X2를 만들면 비용 100이 필요하다. 최종적으로 X2와 C4를 합쳐 최종 파일을 만들면 비용 150이 필요하다. 따라서, 최종의 한 파일을 만드는데 필요한 비용의 합은 60+100+150=310 이다. 다른 방법으로 파일을 합치면 비용을 줄일 수 있다. 먼저 C1과 C2를 합쳐 임시파일 Y1을 만들고, C3와 C4를 합쳐 임시파일 Y2를 만들고, 최종적으로 Y1과 Y2를 합쳐 최종 파일을 만들 수 있다. 이때 필요한 총비용은 70+80+150=300 이다. 소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 프로그램을 작성하시오.
지금까지 풀어본 동적 계획법 중 가장 어려웠다. 이 문제를 파이썬으로 풀면 시간 초과에 막히기 쉬운데 해결방법은 두 가지가 있다. 하나는 pypy로 제출하는 것이다. 같은 로직인데도 다른 언어에서는 괜찮은데 파이썬에서만 시간 초과가 발생한다. 다른 하나는 크누스 알고리즘을 통해 코드를 좀 더 최적화시키는 것이다. 크누스 알고리즘에 대해서 찾아보긴 했는데 '아 이런 게 있구나' 정도로 하고 넘어갔다.
점화식을 찾고도 한참을 헤매다가 겨우 풀었다. 알아놓으면 동적 계획법에서 매우 유용하게 사용할 수 있는 알고리즘이라고 하니 나중에도 생각날 때마다 복기할 생각이다.
문제에 나온 예시를 하나씩 천천히 따라가 보자. C1, C2, C3, C4에 대해서 하나의 파일로 합칠 때 필요한 최소비용을 구해야 한다.
두 개의 파일을 합칠 때 최소 비용은 각 파일 크기의 합이다.
C1, C2의 최소 비용 = 40+30 = 70
C2, C3의 최소 비용 = 30+30 = 60
C3, C4의 최소 비용 = 30+50 = 80
세 개의 파일을 합칠 때부터는 경우의 수를 하나씩 비교해야 한다.
C1, C2, C3의 최소 비용을 구하기 위해 (C1,C2),C3의 비용과 C1,(C2,C3)의 비용을 비교한다.
이 과정을 통해 점화식을 찾을 수 있다. 점화식을 말로 풀어보면 "현재 값은 전 단계 중 최솟값에서 모든 파일의 크기를 더한 것"이다. 여기서 말하는 모든 파일은 해당 단계에 포함되는 파일을 말한다. 예를 들어 C2, C3, C4의 최소 비용을 구할 때 모든 파일은 C2, C3, C4만을 말한다. 이를 점화식으로 표현하기 위해서는 이차원 배열이 필요하며 이차원 배열 dp에 대해서 dp[i][j]는 i번 째 파일부터 j번 째 파일까지 합칠 때 드는 최소 비용이다. 점화식을 수도코드로 표현하면 다음과 같다.
i와 j사이에 있는 모든 k에 대해서 dp[i][j] =min(dp[i][k]+dp[k+1][j])+sum(C[i]~C[j])
위 과정에서 보이다시피 n개의 파일을 합치기 위해서는 2~n-1개의 파일을 합치는데 필요한 최소 비용을 미리 알고 있어야 한다. 그러므로 합치고자 하는 파일의 개수를 하나씩 늘려가며 dp를 채워야 한다.
#11066번 파일 합치기
if __name__ == "__main__":
t = int(input())
for i in range(t) :
sums = [[0]*501 for i in range(501)] # sums[i][j]는 i부터 j까지 합치는데 걸리는 최소 시간
pre_sum = [0]*501 # 총합들
k = int(input())
files = list(map(int,input().split()))
for l in range(len(files)) :
pre_sum[l] = pre_sum[l-1] + files[l]
for page in range(1,k) : # page : start와 end의 거리
for start in range(k+1-page) : # start : 시작
end = start+page # end : 끝
sums[start][end] = 9999999999
pre = pre_sum[end]-pre_sum[start-1] #
for mid in range(start,end) :
sums[start][end] = min(sums[start][end],sums[start][mid]+sums[mid+1][end]+pre) # sums[i][j] = min(sums[i][mid]+sums[mid+1][j])
print(sums[0][k-1])
2. 11049번 행렬 곱셈 순서
문제 크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다. 예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자. - AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다. - BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다. 같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다. 행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.
1번 문제와 매우 유사하게 풀 수 있다. 1번 문제를 바탕으로 다음과 같은 점화식을 구할 수 있다.
i와 j사이에 있는 모든 k에 대해서dp[i][j] = min(dp[i][k]+dp[k+1][j])+mat[start][0]*mat[mid][1]*mat[end][1]
여기서 mat은 행렬의 크기를 저장한 배열이다.
#11049번 행렬 곱셈 순서
if __name__ == "__main__":
n = int(input())
mat = [[0,0]]
for i in range(n) :
a,b = map(int,input().split())
mat.append([a,b])
sums = [[0]*501 for i in range(501)]
sum = [0]*501
for dis in range(1,n) :
for start in range(n+1-dis) :
end = start + dis
sums[start][end] = 999999999
for mid in range(start,end) :
sums[start][end] = min(sums[start][end],sums[start][mid]+sums[mid+1][end]+mat[start][0]*mat[mid][1]*mat[end][1])
print(sums[1][n])
3. 1520번 내리막 길
문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.
지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.
dfs와 dp를 통해 해결하는 문제이다. count는 목적지까지 도달하는 방법의 수를 저장하는 배열이며 동시에 방문 여부를 확인한다. count[x][y]에 -1이 저장되어 있다면 아직 방문하지 않았음을 의미하며 dfs를 수행해야 하며 만약 0 이상이라면 이미 방문한 곳이므로 dfs를 사용하지 않고 dp를 통해 저장된 값을 바로 반환한다.
#1520번 내리막 길
import sys
sys.setrecursionlimit(10 **9)
def dfs(x,y) :
if x == m-1 and y == n-1 : #도착하면 1을 반환
return 1
if count[x][y] != -1 : #이미 방문한 점이라면 바로 반환
return count[x][y]
count[x][y] = 0 #방문 표시
for i in range(4) : #상하좌우에 대해서
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < m and 0 <= ny < n and maps[nx][ny] < maps[x][y] : #이동 가능한 점이라면
count[x][y] += dfs(nx,ny) #개수 추가
return count[x][y]
if __name__ == "__main__":
m,n = map(int,input().split())
maps = []
for i in range(m) :
maps.append(list(map(int,input().split())))
count = [[-1]*n for i in range(m)] #count[x][y]는 (x,y)에서 목적지까지 갈 수 있는 방법의 수
dx = [1,-1,0,0]
dy = [0,0,1,-1]
print(dfs(0,0))
4. 10942번 팰린드롬?
문제 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다. 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그다음, 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니 다를 말해야 한다. 예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.
S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다. S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다. S = 3, E = 3인 경우 1은 팰린드롬이다. S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.
자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.
우선 팰린드롬이 뭔지부터 알아보자. 팰린드롬이란 거꾸로 뒤집어도 똑같은 문자열이 나오는 문자열을 말한다. 이 문제에서는 거꾸로 뒤집어도 똑같은 숫자 배열을 의미한다.
S와 E 사이의 거리를 늘려나가며 팰린드롬인지 아닌지를 구분한다. S와 E가 같다면, 즉 거리가 0이라면 팰린드롬이다. 거리가 1일 때 숫자가 같으면 팰린드롬이다. 거리가 2 이상일 때 양 끝 숫자가 같고 양 끝 숫자를 뺀 나머지 배열이 팰린드롬이라면 양 끝 숫자를 포함한 배열은 팰린드롬이다. 이때 양 끝 숫자를 뺀 나머지 배열이 팰린드롬인지 아닌지를 구분하는 기준은 기존에 저장해놓은 dp를 통해 확인한다.
#10942번 팰린드롬?
import sys
input = sys.stdin.readline
if __name__ == "__main__":
n = int(input())
nums = list(map(int,input().split()))
nums.insert(0,0)
m = int(input())
dp = [[-1]*(n+1) for i in range(n+1)]
for dis in range(n) :
for start in range(1,n+1-dis) :
end = start + dis
if start == end :
dp[start][end] = 1
elif start+1 == end :
if nums[start] == nums[end] :
dp[start][end] = 1
else :
dp[start][end] = 0
else :
if nums[start] == nums[end] and dp[start+1][end-1] == 1 :
dp[start][end] = 1
else :
dp[start][end] = 0
for i in range(m) :
start, end = map(int,input().split())
print(dp[start][end])
5. 2629번 양팔저울
문제 양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다. 무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다. 구슬이 3g인 경우 아래 <그림 1>과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다. <그림 2>와 같은 방법을 사용하면 구슬이 5g 인지도 확인할 수 있다. 구슬이 2g이면 주어진 추를 가지고는 확인할 수 없다. 추들의 무게와 확인할 구슬들의 무게가 입력되었을 때, 주어진 추만을 사용하여 구슬의 무게를 확인할 수 있는지를 결정하는 프로그램을 작성하시오.
처음에는 추가 1개인 경우부터 n개인 경우까지 모든 경우의 수를 전부 세려고 했으나 추가 하나씩 추가될 때마다 연관성을 찾지 못해서 그만뒀다. 다음으로 다음 방법을 생각했다.
추가 하나씩 추가될 때마다 세 가지 상황 중 하나가 발생한다.
추가한 추를 구슬이 없는 쪽에 놓는 경우
추가한 추를 놓지 않는 경우
추가한 추를 구슬이 있는 쪽에 놓는 경우
마치 자식 노드가 세 개인 트리를 떠올릴 수 있다. 모든 경우에 대해 확인 가능한 추의 무게를 추가한다. 그리고 트리를 따라 쭉 뻗어 나가다가 추의 개수가 n을 초과하는 순간 종료시킨다.
여기서 구슬의 무게는 40000g 이하이며 추가 측정할 수 있는 최대 크기는 500g*30개 = 15000g이므로 구슬의 무게가 15000g을 초과하는 경우 또한 측정할 수 없는 구슬이다.
#2629번 양팔저울
def btr(weight_count, weight_now) :
if dp[weight_count][weight_now] == 1 :
return
else :
dp[weight_count][weight_now] = 1
if weight_count >= n :
return
btr(weight_count+1,weight_now+weight[weight_count]) # 추를 추가하고 구슬 없는 쪽에 놓는 경우
btr(weight_count+1,weight_now) # 추를 추가했지만 아예 놓지 않는 경우
btr(weight_count+1,abs(weight_now-weight[weight_count])) # 추를 추가하고 구슬 있는 쪽에 놓는 경우
if __name__ == "__main__":
n = int(input())
weight = list(map(int,input().split()))
bead_num = int(input())
bead_weight = list(map(int,input().split()))
dp = [[0]*(len(weight)*500+1) for i in range(len(weight)+1)]
btr(0,0)
for i in bead_weight :
if i > 15000 : # 구슬의 무게가 15000 초과하면 측정 불가능
print("N",end=' ')
elif dp[n][i] == 1 :
print("Y",end=' ')
else :
print("N",end=' ')
6. 2293번 동전 1
문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
k가 10이라면 1부터 10까지 모든 경우에 수에 대해서 각 동전들을 하나씩 추가해나가며 개수를 확인해야 한다. 문제에 나와있는 예제를 보며 풀이해본다.
동전의 종류는 3가지며, 각 1원, 2원, 5원이다. 만들어야 하는 가치의 합은 10원이다. 3원까지만 만든다고 생각해보자.
1원을 만드는 경우는 1원을 하나쓰는 한 가지 경우이다. 2원을 만드는 경우는 1원을 두번쓰거나 2원을 1번쓰는 총 두 가지 경우이다. 3원을 만드는 경우는 1원을 세번쓰거나 2원을 한번, 1원을 한번 쓰는 총 두 가지 경우이다. 이때 2원과 1원을 한 번씩 쓰는 경우를 주목한다. 3원을 만들기 위해 2원을 한번 사용하면 1원이 남는다. 남은 1원에 대해서 만들 수 있는 경우의 수를 생각할 수 있다. 즉 3원을 만들기 위해 2원을 사용할 경우, 1원이 만들어지는 경우의 수로 문제가 바뀌게 된다. 4원을 만드는 경우를 생각해보자. 1원을 네 번 쓰는 경우, 2원을 두 번 쓰는 경우, 2원 한 번과 1원 두 번을 쓰는 경우 총 세 가지 경우가 나온다. 만약 2원을 사용할 경우 남은 2원을 만드는 경우의 수를 생각할 수 있다. 즉 1,2,5원 동전에 대해서 어떠한 코인 c원을 사용할 경우 k원을 구하는 경우의 수는 이전까지 구했던 k원을 구하는 경우의 수와 k-c원을 구하는 경우의 수를 합친 것과 같다.
위 과정을 점화식으로 바꾸면 다음과 같다. 현재 동전까지 k원을 구한 경우의 수를 저장하는 배열 dp와 동전들의 집합 coin에 대해서 dp[k] = dp[k] + dp[k-coin]이다. dp는 계속 덮어써서 사용할 수 있기 때문에 메모리 제한을 회피할 수 있다.
#2293번 동전 1
if __name__ == "__main__":
n,k = map(int,input().split())
coin = []
for i in range(n) :
coin.append(int(input()))
dp = [0]*10001
dp[0]=1
for c in coin :
for k_ in range(c,k+1) :
dp[k_] += dp[k_-c]
print(dp[k])
#c
# 1 2 3 4 5 6 7 8 9 10 k_
#1 1 1 1 1 1 1 1 1 1 1
#2 0 1 1 2 2 3 3 4 4 5
#5 0 0 0 0 1 1 2 2 3 4
# 10
7. 7579번 앱
문제 우리는 스마트폰을 사용하면서 여러 가지 앱(App)을 실행하게 된다. 대개의 경우 화면에 보이는 ‘실행 중’인 앱은 하나뿐이지만 보이지 않는 상태로 많은 앱이 '활성화'되어 있다. 앱들이 활성화되어 있다는 것은 화면에 보이지 않더라도 메인 메모리에 직전의 상태가 기록되어 있는 것을 말한다. 현재 실행 중이 아니더라도 이렇게 메모리에 남겨두는 이유는 사용자가 이전에 실행하던 앱을 다시 불러올 때에 직전의 상태를 메인 메모리로부터 읽어 들여 실행 준비를 빠르게 마치기 위해서이다. 하지만 스마트폰의 메모리는 제한적이기 때문에 한 번이라도 실행했던 모든 앱을 활성화된 채로 메인 메모리에 남겨두다 보면 메모리 부족 상태가 오기 쉽다. 새로운 앱을 실행시키기 위해 필요한 메모리가 부족해지면 스마트폰의 운영체제는 활성화되어 있는 앱들 중 몇 개를 선택하여 메모리로부터 삭제하는 수밖에 없다. 이러한 과정을 앱의 ‘비활성화’라고 한다. 메모리 부족 상황에서 활성화 되어 있는 앱들을 무작위로 필요한 메모리만큼 비활성화하는 것은 좋은 방법이 아니다. 비활성화된 앱들을 재실행할 경우 그만큼 시간이 더 필요하기 때문이다. 여러분은 이러한 앱의 비활성화 문제를 스마트하게 해결하기 위한 프로그램을 작성해야 한다 현재 N개의 앱, A1, ..., AN이 활성화 되어 있다고 가정하자. 이들 앱 Ai는 각각 mi 바이트만큼의 메모리를 사용하고 있다. 또한, 앱 Ai를 비활성화한 후에 다시 실행하고자 할 경우, 추가적으로 들어가는 비용(시간 등)을 수치화 한 것을 ci 라고 하자. 이러한 상황에서 사용자가 새로운 앱 B를 실행하고자 하여, 추가로 M 바이트의 메모리가 필요하다고 하자. 즉, 현재 활성화 되어 있는 앱 A1, ..., AN 중에서 몇 개를 비활성화하여 M 바이트 이상의 메모리를 추가로 확보해야 하는 것이다. 여러분은 그중에서 비활성화했을 경우의 비용 ci의 합을 최소화하여 필요한 메모리 M 바이트를 확보하는 방법을 찾아야 한다.
동적 계획법의 대표적인 문제인 배낭 문제, 냅색 문제를 응용해서 풀 수 있는 문제이다.
메모리 M만큼 확보하는 c 합의 최솟값을 구해야 한다. c와 앱을 하나씩 늘려가며 현재 c에 대해서 확보 가능한 최대 메모리를 구한다. 구하는 과정에서 냅색 알고리즘을 활용할 수 있다.
어떠한 앱에 대해서 앱을 비 활성할 때 현재 앱을 비 활성하는 경우와 비 활성하지 않는 경우 중 더 많은 메로리를 확보하는 경우를 선택하면 된다. 이를 점화식으로 표현하면 다음과 같다. i는 현재 앱, j는 c이며 dp[i][j]는 i번 째 앱까지 비활성화를 고려하고 비용은 j일 때 확보가능한 최대 메모리이다.
#7579번 앱
if __name__ == "__main__":
n,m = map(int,(input().split())) #n개의 앱, 필요한 메모리 m
memory = list(map(int,input().split())) #n개의 앱들이 현재 사용 중인 메모리
c = list(map(int,input().split()))#비활후 다시 활성화 했을 때 필요한 비용 c
c_sum = sum(c)
dp = [[0]*(c_sum+1) for i in range(n)] #
for i in range(c_sum+1) :
if i >= c[0] :
dp[0][i] = memory[0]
for i in range(1,n) :
for j in range(c_sum+1) :
if j < c[i] :
dp[i][j] = dp[i-1][j]
else :
dp[i][j] = max(dp[i-1][j], memory[i]+dp[i-1][j-c[i]]) #현재 앱을 비활성화하는 경우와 현재 앱을 비활성화하지 않는 경우
for i in range(c_sum+1) :
if dp[n-1][i] >= m :
print(i)
break
# 현재 c 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
# m c
# 30 3 00 00 00 30 30 30 30 30 30 30 30 30 30 30 30 30 최대 c만큼 비활성화가 가능하다고 했을 때 확보 가능한 최대 메모리
# 10 0 10 10 10 40 40 40 40 40 40 40 40 40 40 40 40 40
# 20 3 10 10 10 40 40 40 60 60 60 60 60 60 60 60 60 60
# 35 5 10 10 10 40 40 45 60 60 75 75 75 95 95 95 95 95
# 40 4 10 10 10 40 50 50 60 80 80 85 100 100 115 115 115 135
