45656이란 수를 보자. 이 수는 인접한 모든 자릿수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)
step_num은 계단의 개수마다 계단 수를 저장하는 배열이다. 길이가 N인 계단 수 중 i번 째 계단을 결정할 때, i번 째 계단으로 올 수 있는 경우의 수를 저장한다. 0과 인접한 수는 1밖에 없다. 그러므로 i번 째 계단이 0인 경우의 수는 i-1번째 계단이 1인 경우의 수와 같다.9와 인접한 수는 8밖에 없다. 그러므로 i번 째 계단이 9인 경우의 수는 j-1번째 계단이 8인 경우의 수와 같다. 그 외의 수 x와 인접한 수는 j-1과 j+1이다.그러므로 i번 째 계단이 x인 경우의 수는 i-1번째 계단에서 j-1인 경우의 수와 j+1인 경우의 수의 합과 같다.
i번 째 계단이 0인 수의 개수 == i-1번 째 계단이 1인 수의 개수
i번 째 계단이 9인 수의 개수 == i-1번 째 계단이 8인 수의 개수
i번 째 계단이 j인 수의 개수 == (i-1번째 계단이 j-1인 수의 개수) + (i-1번 째 계단이 j+1인 수의 개수)
#10844번 쉬운 계단 수
n = int(input())
step_num = [[0]*(10) for i in range(n+1)]
for i in range(1,10) :
step_num[1][i] = 1
for i in range(2,n+1) :
step_num[i][0] = step_num[i-1][1] # 0과 인접한 수는 1
step_num[i][9] = step_num[i-1][8] # 9와 인접한 수 8
for j in range(1,9) :
step_num[i][j] = (step_num[i-1][j-1] + step_num[i-1][j+1])%1000000000 # j와 인접한 수는 j-1, j+1
print(sum(step_num[n])%1000000000)
10. 2156번 포도주 시식
문제
효주는 포도주 시식회에 갔다. 그곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.
포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.
7번 계단 오르기와 거의 똑같은 문제이다. 차이점은 계단 오르기에서는 마지막 계단을 꼭 밟아야 하지만, 포도주 시식은 마지막 포도주를 꼭 마시지 않아도 된다.
포도주가 하나 또는 두 개일 경우 모든 포도주를 마시는 게 가장 많은 양의 포도주를 마시는 것이다. 포도주가 세 개 이상일 경우, n개의 포도주 중 i번 째 포도주를 마실지 말지 결정할 때, 세 가지 경우 중 가장 큰 값을 선택해야 한다. 세 가지 경우는 다음과 같다.
i번 째 포도주와 i-1번째 포도주를 마시고, i-3번째 포도주까지의 가장 많이 마시는 경우
i번 째 포도주를 마시고, i-2번째 포도주까지의 가장 많이 마시는 경우
i번 째 포도주를 안 마시고, i-1번째 포도주까지의 가장 많이 마시는 경우
#2156번 포도주 시식
n = int(input())
podoju = [] #포도주
for i in range(n) :
podoju.append(int(input()))
point = [False]*n
if n == 1 : #포도주 하나
point[0] = podoju[0]
elif n == 2 : #포도주 둘
point[1] = podoju[0] + podoju[1]
else : #포두주 셋 이상
point[0] = podoju[0]
point[1] = podoju[0] + podoju[1]
point[2] = max(podoju[1]+podoju[2],podoju[0]+podoju[2], podoju[0] + podoju[1])
for i in range(3, n) :
point[i] = max(point[i-1], podoju[i]+podoju[i-1]+point[i-3], podoju[i]+point[i-2])
#i번 째 포도주를 마실 차례 일 때 1. i번째와 i-1번째를 마시고 i-3까지의 최댓값 or i번째를 마시고 i-2까지의 최댓값 or i번째를 안마시고 i-1까지의 최댓값
print(point[n-1])
11. 11053번 가장 긴 증가하는 부분 수열
문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10,20, 10,30, 20,50} 이고,길이는 4이다.
LIS로도 많이 알려진 유명한 문제이다. arr은 수열이 저장되는 공간이다. 증가하는 부분 수열을 만족시키기 위해 두 수 i, j에 대해서 i <j일 때 arr [i] < arr[j]를 만족시켜야한다. 즉 arr[i] < arr [j]라면 arr [j]는 증가하는 부분 수열에 추가할 수 있다. length는 부분 수열의 길이를 저장하는 배열이며 length[x]는 수열 중 x번 째 숫자까지의 최장 증가수열의 길이이다. 만약 arr[i] < arr[j]라면 arr[j]는현재최장 증가수열 추가할 수 있으면 이 때 부분 수열의 길이는 length [i]+1이다. 이 때 length[j]는 다음 두 가지 중 더 큰 값이다.
i번 째 숫자까지의 최장 증가 수열 길이에 1을 더한 값 : length[i]+1
그전에 저장되어있던 j번 째 숫자까지의 최장 증가수열 길이 : length [j]
#11053번 가장 긴 증가하는 부분 수열
n = int(input())
arr = []
arr = list(map(int,input().split()))
length = [1]*n
for i in range(n) :
for j in range(i,n) :
if arr[i] < arr[j] :
length[j] = max(length[i]+1,length[j])
print(length)
print(max(length))
12. 11054번 가장 긴 바이 토닉 부분 수열
문제
수열 S가 어떤 수 Sk를 기준으로 S1< S2 < ...Sk-1< Sk> Sk+1 > ...SN-1> SN을 만족한다면, 그 수열을 바이 토닉 수열이라고 한다.
예를 들어, {10, 20,30, 25, 20}과 {10, 20, 30,40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.
수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.
11번 가장 긴 증가하는 부분 수열의 연장선이다. 수열 중 원소들이 계속 감소하는 수열을 감소 수열이라고 하자. 바이토닉 수열은 증가 부분 수열과 감소 부분 수열을 합친 것이라고 할 수 있다. 이때 어떤 배열에 대해서 감소 부분 수열을 구하라는 말은 어떤 배열의 역순에 대해서 증가 부분 수열을 구하라는 말과 같다.
입력되는 배열에 대해서 11번과 마찬가지로 증가수열을 구하고, 입력되는 배열을 뒤집은 배열에 대해서 똑같이 증가 수열을 구한다. 구한 수열들의 각 길이를 배열 length_up과 length_down에 저장한다. 즉 index i에 대해서 length_up [i]는 i번째 수까지의 최장 증가수열의 길이, length_down [i]는 i번 째 수부터의 최장 감소 수열의 길이이다. length_up [i]과 length_down [i]를 더하면 i번 째 수를 기준으로 바이 토닉 부분 수열의 길이를 구할 수 있다. 이때 i번 째 수는 중복되어 세지기 때문에 1을 뺀다.
#11054번 가장 긴 바이토닉 부분 수열
n = int(input())
arr_up = []
arr_down = []
arr_up = list(map(int,input().split())) #원래 수열
arr_down = list(reversed(arr_up)) # 원래 수열을 뒤집음
length_up = [1]*n
length_down = [1]*n
length = []
for i in range(n) :
for j in range(i,n) :
if arr_up[i] < arr_up[j] : #원래 수열의 가장 긴 증가하는 부분 수열
length_up[j] = max(length_up[i]+1,length_up[j])
if arr_down[i] < arr_down[j] : #뒤집은 수열의 가장 긴 증가하는 부분 수열 == 원래 수열의 가장 긴 감소하는 부분 수열
length_down[j] = max(length_down[i]+1, length_down[j])
for i in range(n) :
length.append(length_up[i] + list(reversed(length_down))[i]) # 각 인덱스마다 두 개 길이를 더해 줌
print(max(length)-1) # 인덱스는 중복되어 두번씩 세지기 때문에 하나를 뺌
13. 2565번 전깃줄
문제
두 전봇대 A와 B 사이에 하나둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.
예를 들어, <그림 1>과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다.
전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램을 작성하시오.
처음 봤을 때는 많이 어려웠다. 알고리즘을 어떻게 짜야 하나 많이 고민해봤고 여러 가지를 시도해봤는데 결국 이 문제도 LIS 문제이다. 전깃줄이 교차하지 않으려면 전깃줄을 정렬했을 때 전깃줄의 위치가 A와 B에서 같은 순서에 있으면 된다. 예를 들어 어떤 두 전봇대의 전깃줄이 교차하지 않을 때, 어떤 전 길 줄이 A에서 x번 째로 큰 위치에 존재한다면, B에서도 무조건 x번 째로 큰 위치에 존재한다. 문제에서 요구하는 답은 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수이다. 이를 반대로 말하면 전깃줄이 존재할 수 있는 최대 개수이다. 즉 입력되는 전깃줄들을 A 위치를 기준으로 정렬했을 때 B를 기준으로 LIS를 구하면 된다.
#2565번 전깃줄
n = int(input())
line = []
for i in range(n) :
line.append(list(map(int,input().split())))
line_count = [1]*n
line.sort(key = lambda x : x[0])
for i in range(n) :
for j in range(i) :
if line[i][1] > line[j][1] :
line_count[i] = max(line_count[i],line_count[j]+1)
print(n-max(line_count))
14. LCS
문제
LCS(Longest Common Subsequence, 최장 공통부분 수열) 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
동적 계획법을 배울 때 자주 나오는 LCS 문제이다. 두 문자열에 대해서 한 글자씩 비교해주며 해당 글자까지의 LCS를 계속 기록한다. 같은 글자가 나오면 1을 추가해주며 그렇지 않으면 직전까지의 LCS 중 가장 큰 값으로 기록한다. 이를 표로 보면 다음과 같다.
arr
A
C
A
Y
K
P
C
0
1
1
1
1
1
A
1
1
2
2
2
2
P
1
1
2
2
2
3
C
1
2
2
2
2
3
A
1
2
3
3
3
3
K
1
2
3
3
4
4
arr은 LCS를 기록하는 2차원 배열이다. arr [i][j]는첫 번째 문자열의 i번 째 글자까지 와 두 번째 문자열의 j번 째 글자까지의 LCS이다.
첫 번째 문자열의 i번 째 글자 == 두 번째 문자열의 j번 째 글자 : arr [i][j] = arr [i-1][j-1]+1
첫 번째 문자열의 i번 째 글자!= 두 번째 문자열의 j번 째 글자 :arr [i][j] = max(arr [i][j-1], arr [i-1][j])
#9251번 LCS
string_1 = input()
string_2 = input()
arr = [[0]*(len(string_2)+1) for i in range(len(string_1)+1)]
#각 배열을 하나씩 증가하면서 LCS의 개수를 저장할 배열
for i in range(1,len(string_1)+1) :
for j in range(1,len(string_2)+1) :
if string_1[i-1] == string_2[j-1] :
arr[i][j] = arr[i-1][j-1]+1 # 두 문자가 같다면 이전까지 LCS길이에서 +1
else :
arr[i][j] = max(arr[i-1][j],arr[i][j-1]) # 두 문자가 다르다면 이전 LCS 중 가장 큰 값
print(max(arr[len(string_1)]))
15. 1912번 연속합
문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
n개의 정수 중 i번 째를 연속으로 더할지 말지 결정해야 한다. 반대로 생각해보자. i번 째 숫자 입장에서 i-1번째 숫자까지의 연속된 수의 합에 더해지는 게 더 이득일까, 새로 본인부터 다시 더해나가는게 더 이득일까. i-1번 째 숫자까지의 연속된 수의 합이 음수만 아니라면 무조건 더해지는게 이득이다. 다음 표를 보자.
i
0
1
2
3
4
5
6
7
8
9
num
10
-4
3
1
5
6
-35
12
21
-1
arr
10
6
9
10
15
21
-14
12
33
32
num배열은 입력받은 숫자이며 arr배열은 i번 째 숫자를 무조건 선택할 때 가장 큰 합을 저장하는 배열이다. i=1일 때를 보자. num [1]은 -4지만 num [1] 입장에서는 arr [0]과 더해지는 것이 무조건 이득이기 때문에 arr[1] = arr[0] + num [1]이다. i=7 일 때를 보자. arr [6]은 -14이다. arr [7] 입장에서는 -14를 더하는 것은 무조건 손해를 본다. 때문에 연속으로 더해지지 않고 자기 자신보다 새로 더해나가는 게 더 큰 값을 만들 수 있다. 즉 arr [i-1]이 음수라면 무조건 이전 연속적인 합에 더해지지 않고 새롭게 시작한다.
#1912번 연속합
n = int(input())
num_arr = list(map(int,input().split()))
arr = [0]*n
arr[0] = num_arr[0]
for i in range(n) :
arr[i] = max(num_arr[i],arr[i-1]+num_arr[i]) #이전까지의 합이 음수라면 현재 수와 더하지 않고 새로 시작
print(max(arr))
16. 12865번 평범한 배낭 문제
이 문제는 아주 평범한 배낭에 관한 문제이다.
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.
배낭문제 또한 동적 계획법에서 매우 유명한 문제이다. 배낭의 무게를 하나씩 늘려가면 각 물건마다 물건을 가방에 넣을 수 있는지 확인하고 배낭의 무게를 늘릴 때마다 가치의 최댓값을 기록한다. 만약 어떤 물건을 넣을 수 있다면 물건을 넣고 남은 무게로 넣을 수 있는 가치의 최댓값을 기록해둔 배열에서 가져와 더 한다. 이 값과 어떤 물건을 넣지 않았을 때의 가치 중 더 큰 값으로 배열에 기록한다. 다음 표를 보자.
bag
0
1
2
3
4
5
6
7
weight
value
6
13
0
0
0
0
0
0
13
13
4
8
0
0
0
0
8
8
13
13
3
6
0
0
0
6
8
8
13
14
5
12
0
0
0
6
8
8
12
14
위 표에서 파란색 13을 보자. 가방 용량은 6으로 무게가 4인 물건을 넣을 수 있지만 무게가 4인 물건을 넣지 않고 무게가 6인 물건을 넣는 게 가치가 더 크기 때문에 무게가 4인 물건은 넣지 않는다. 즉 bag [2][6] = bag [2-1][6]이다.
빨간색 14를 보자. 무게가 3인 물건을 넣고, 남은 공간에서 무게가 4인 물건을 더 넣을 수 있어 가치가 14가 된다. 즉 bag [3][7] = 현재 value + bag [3-1][7-현재 weight]이다.
현재 물건을 넣을 수 있다면 : bag [i][j] = max(현재 value+bag [i-1][j-현재 weight], bag [i-1][j])
현재 물건을 넣을 수 없다면 : bag [i][j] = bag [i-1][j]
#12865번 평범한 배낭
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
wv = [[0]*2 for i in range(n+1)]
start = 98765
bag = [[0]*(k+1) for i in range(n+1)]
for i in range(1,n+1) :
wv[i] = list(map(int,input().split()))
start = min(start,wv[i][0])
for j in range(start,k+1) :
if wv[i][0] <= j :
bag[i][j] = max(wv[i][1]+bag[i-1][j-wv[i][0]],bag[i-1][j])
else :
bag[i][j] = bag[i-1][j]
print(bag[n][k])
