동적계획법(Dynamic Programing) - 백준 1149,1932,2579,2156,11053,11054,2565,12865,9251
동적계획법 일명 dp는 진짜 좀 어려운 것 같다..
하루 온 종일 생각해도 점화식이나 data를 담을 d배열의 구조를 생각해내지못하면 절대 풀 수 없다
그래서 정복하기까지 꽤 오래 걸렸는데
다른 사람들의 답안을 참고하여 푼 문제도 많다..
문제에 주석을 달면서 복습해야지...
https://www.acmicpc.net/problem/1149
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
집마다 각각의 색깔을 칠하고 색칠할 때마다 비용이 발생한다.
특정 조건을 만족하면서 비용의 최소값을 구하는 문제였는데
dp에서 자주 사용하는 d배열의 구조가 여기서 등장한다.
나는 전에 한 번 본 적이 있지만 완전히 내 것이 되지 않았는지 떠올리지 못했다.
이번 기회를 계기로 내걸로 만들기 약속!
#집의 수 n
n = int(input())
# 집마다 각 색깔별 가격 받아오기
li = [list(map(int,input().split())) for _ in range(n)]
#dp정답배열로 사용할 nput
nput = [[0]*3 for i in range(n+1)]
#여기서 0,1,2는 각각 R,G,B이다.
#n번째 집의 색깔이 R일경우, G일경우 B일경우를 모두 계산한다.
#만약 R이라면 그 전 집인 n-1번째 집은 G혹은 B로 칠한 값의 최소값이 와야한다.
#만약 G라면 n-1번째 집이 R또는 B로 칠한 값의 최소로 오면 된다.
#이러한 논리로 인해 아래와 같은 점화식을 만들 수 있다.
for i in range(1,n+1) :
nput[i][0] += min(nput[i-1][1],nput[i-1][2]) + li[i-1][0]
nput[i][1] += min(nput[i-1][0],nput[i-1][2]) + li[i-1][1]
nput[i][2] += min(nput[i-1][0],nput[i-1][1]) + li[i-1][2]
#모든 연산이 끝나고 마지막 집을 R,G,B로 칠한 경우 중에 최소를 출력한다
print(min(nput[n]))
https://www.acmicpc.net/problem/1932
1932번: 정수 삼각형
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
www.acmicpc.net
이것도 점화식을 생각해내는데 혼자서 엄청 고민한 문제이다..
난 더 높은 수준의 난이도를 풀어내는 실력을 원하는데 고작 실버1의 난이도에서 이렇게 해메는 내가 싫었다..
그래도 풀어내서 짜릿했다
#삼각형 높이
cases = int(input())
#삼각형의 값을 담을 배열 li
li = [list(map(int,input().split())) for _ in range(cases)]
#맨 아래에서부터 위로 더해나가는 방법이다
#아래에서 윗항목으로 올라갈 수록 가능한 연산 범위 내에서 가장 큰 값으로 대체해줄 것이다.
for i in range(len(li)-1,0,-1) :
arr = li[i]
result = [] #더해준 모든 값을 담을 리스트
for j in range(len(arr)) :
if j == 0 : #가장 첫 원소라면 무조건 그 윗단계의 가장 첫 원소만 셈을 할 수 있다.
num = arr[j] + li[i-1][0]
result.append(num) #result에 연산값 저장 후 continue
continue
if j == len(arr) - 1 : #가장 끝 원소라면 그 윗단계의 가장 마지막 원소와 셈을 해야한다.
num = arr[j] + li[i-1][j-1]
result[len(result) - 1 ] = max(result[len(result) - 1 ],num)
continue
num1 = arr[j] + li[i-1][j-1] #대각선으로 뻗어나가므로 첫 번째 숫자
num2 = arr[j] + li[i-1][j] #두 번째 숫자
result[j-1] = max(result[j-1],num1)
result.append(num2)
li[i-1] = result #li배열의 윗배열을 result로 대입
print(li[0][0])https://www.acmicpc.net/problem/2579
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
계단오르기도 하루종일 걸렸던 부분이다
처음에 문제 조건을 제대로 이해하지 못해서 시간을 엄청 날렸다
그럼에도 점화식을 어설프게 구해서 다른 사람의 풀이를 참조한 문제..ㅠ
#계단 수 n
n = int(input())
#1번부터 시작할 것이므로 0을 가진 li생성
li = [0]
for _ in range(n) :
li.append(int(input()))
#정답으로 사용할 d list
d = [0] * (n+1)
#계단 수가 1이면 첫번째 값 출력
if n == 1 :
print(li[1])
#계단 수가 2라면 두 계단을 모두 밟은 값 출력
elif n == 2 :
print(li[1] + li[2])
#d[1]과 d[2]에는 최대값을 수동으로 넣어준다.
#d[3]은 두 가지 경우가 있는데 그 중 최대 값을 넣어준다.
#4번째 계단으로 가는 경우를 생각해보자
#계단은 3개이상 연속으로 밟을 수 없다.
#그러므로 1번,3번,4번 혹은 1번,2번,4번 이렇게 밟아야 한다.
#이를 점화식으로 나타내면 d[1] + li[3] +li[4], d[2] + li[4])이다.
#여기서 3번째 계단을 밟는 과정에서 d[3]을 쓰지 않는 이유는
#3번째 계단을 밟을 때 2번과3번을 밟은 값이 d[3]에 있으면 조건에 위배되기 때문이다.
else :
d[1] = li[1]
d[2] = li[1] + li[2]
d[3] = max(li[1] + li[3], li[2]+li[3])
for i in range(4,n+1) :
d[i] = max(d[i-3] + li[i-1] +li[i],d[i-2] + li[i])
print(d[n])여기서 나는 맨 마지막 주석인 d[3]을 쓰지 않는 이유를 찾지 못해 계속 d[3]을 써서 풀지 못했었다..
https://www.acmicpc.net/problem/2156
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
포도주 문제도 꽤 헤메었다..
안먹고 넘기는 경우를 계산하기가 어려웠는데
위에서 RGB를 풀었던 방법과 비슷하게 풀어넘기면 됐다...
많이 배워간다..
cases = int(input())
li = [int(input()) for _ in range(cases)]
#1부터 시작할 것이므로 맨 앞에0을 넣어준다
li.insert(0,0)
#여기서 d는 3개의 원소를 갖는다
#1번째 원소는 처음 마시는 잔의 경우
#2번째 원소는 두 번째 마시는 잔의 경우
#3번째 원소는 안마시는 경우이다.
d = [[0,0,0] for _ in range(cases+1)]
if cases == 1 :
print(li[1])
else :
d[1] = [li[1],0,0]
for i in range(2,cases+1) :
#첫 번째로 마신다면 이전에 잔에서 안마신 경우에만 해당하므로 해당 값에서 더해준다
d[i][0] = d[i-1][2] + li[i]
#두 번째로 마신다면 이전에서 첫 잔을 마신 값인 d[i-1][0]과 더해준다
d[i][1] = d[i-1][0] + li[i]
#안 마신다면 이전 잔의 최대값을 넣어준다
d[i][2] = max(d[i-1][0],d[i-1][1],d[i-1][2])
print(max(d[cases]))https://www.acmicpc.net/problem/11053
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
LIS를 구하는 문제라고 불리는 이 문제도
전형적인 DP의 유형중에 하나이다
점화식만 생각해낸다면 쉽게 풀 수 있는 문제이지만
난 이걸 생각하는데 5시간이 넘게 걸렸다..
n = int(input())
li = list(map(int,input().split()))
d = [1] * n
#1부터 n까지 순회하고
for i in range(1,n) :
#0부터 i까지 순회할 것이다.
for j in range(i) :
if li[i] > li[j] : #증가해야하므로 i번째의 값이 j보다 크다면
#d[i]는 d[j]에서 1을 더해준 값과(증가로 친다) 현재 d[i]값 중에 큰 값을 쓴다.
d[i] = max(d[j] + 1, d[i])
print(max(d))https://www.acmicpc.net/problem/11054
11054번: 가장 긴 바이토닉 부분 수열
첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)
www.acmicpc.net
바이토닉 수열은 양 끝에서 증가하는 부분수열이라고 표현하면 쉬운데
LIS를 풀자마자 음..이걸 뒤집어서 계산한 다음에 전부 합을 더해주면
각 원소마다 바이토닉 수열을 구할 수 있으니까 전부 더해서 최대값 출력해주면 되겠네?
하고 풀었더니 바로 맞은 문제이다..
cases = int(input())
li = list(map(int,input().split()))
d = [1] * cases
for i in range(1,cases) :
for j in range(i) :
if li[i] > li[j] :
d[i] = max(d[j]+1,d[i])
#d는 순방향 LIS
li.reverse()
d1 = [1] * cases
for i in range(1,cases) :
for j in range(i) :
if li[i] > li[j] :
d1[i] = max(d1[j]+1,d1[i])
d1.reverse()
#d1은 역방향 LIS / 원소 순서를 맞추기 위해 reverse사용
for i in range(len(d)) :
d[i] += d1[i] #모든 항목을 더해줌
#max에서 1을 빼는 이유는 만나는 지점이 2번 계산되므로 1을 빼준다
print(max(d)-1)https://www.acmicpc.net/problem/2565
2565번: 전깃줄
첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는
www.acmicpc.net
이 문제도 엄청 오래걸렸다..
왼쪽 전봇대 오른쪽 전봇대 두 값보다 둘 다 크거나 둘 다 작거나로 계산했는데
이렇게 복잡하게 할 필요 없이 한쪽을 정렬해놓고 LIS로 풀면 되는 문제였다.
n = int(input())
line = [list(map(int,input().split())) for _ in range(n)]
line.sort(key= lambda x : x[0])
d = [1] * n
for i in range(n) :
for j in range(i+1) :
if line[j][1] < line[i][1]:
d[i] = max(d[j] + 1, d[i])
#line정렬후 구한 lis의 최대값에서 총 전기줄의 갯수와 셈을 해준다
print(n-max(d))https://www.acmicpc.net/problem/12865
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
평범한 배낭이라 해놓고 너~~~~~무 어려웠던 문제..
무게와 가치가 주어지는데 순회할 변수를 뭐로 설정해야 할 지와
dp에서 사용할 d배열의 구조를 생각해내는데 하루 종일 붙잡아도 안돼서 다른 사람들의 풀이를 참고했다..
가치를 높여가면서 값을 계산해주는 2차원구조였는데 나에겐 너무 어려웠다..
cases,bag = map(int,input().split())
items = [list(map(int,input().split())) for _ in range(cases)]
#d는 가방의 무게에 따른 가치의 최대값들을 담을 것이다
d = [[0]*(bag+1) for _ in range(cases+1)]
items.insert(0,[0,0])
#가방을 순회한다
for i in range(1,cases+1) :
#무게를 순회한다
for j in range(1,bag+1) :
#w는 무게 v는 가치이다
w = items[i][0]
v = items[i][1]
#j가 w보다 작다면 i번째 가방에서 무게가 j일때 갖는 value의 최대는
#이전 가방의 무게가 j일때 갖는 value와 같다.
#왜냐하면 새로운 가방을 추가하지 않았기 때문이다.
if j < w :
d[i][j] = d[i-1][j]
#반대로 무게 j가 w보다 크다면 w를 넣거나 넣지않을 수 있다.
#넣지 않는 경우는 이전 가방인d[i-1]에서 무게j 즉, d[i-1][j]와
#w를 추가해야하므로 이전 가방에서 w만큼 뺀 값의 가치d[i-1][j-w]와
#현재 가방의 가치에 해당하는v를 더한 d[i-1][j-w] + v가 된다.
# max를 사용해d[i-1][j] 과 d[i-1][j-w] + v을 비교하여
#더 큰 값을 넣어주면 가방을 넣거나 넣지않는 연산을 처리한 셈이다.
else :
d[i][j] = max(d[i-1][j],d[i-1][j-w] + v)
print(d[cases][bag])https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
이번엔 LCS였는데 이것도 한참 고민했다
거의 이틀 고민했는데 못풀었다.. 반례들을 끼워맞추느라 틀렸던 것 같다...
이것도 다른 사람의 정답을 참고했는데 cache를 사용해 계산했다
a = input()
b = input()
#두 개중 하나의 길이만큼 cache생성
cache = [0] * len(b)
for i in range(len(a)) :
cnt = 0
for j in range(len(b)) :
#cnt가 cache보다 작으면 cnt에 값을 대입하고 끝난다.
#이 과정에서 a[i]와 b[j]가 문자열이 같더라도
#cnt가 더 작으면 추가하지 않는 연산을 한 셈이다.
if cnt < cache[j] :
cnt = cache[j]
#이 조건으로 넘어온다면 대상 문자열과 이전 문자열간 cnt는 같거나 그 이상이라는 뜻이다.
#그리고 문자열이 일치한다면 cache의 값에 1을 추가해준다.
elif a[i] == b[j] :
cache[j] = cnt + 1
print(max(cache))
이렇게 DP에 관한 문제들을 여럿 풀어봤는데 아직 감이 오질 않는다..
더 많이 풀어봐야 할 것 같다...
백준 단계별로 풀어보기에서 진행중인데 이게 대공사에 들어가면서
DP의 난이도 책정이 한참 높아졌다.. 다시 낮은 단계부터 차근차근 풀어야지...