tose33

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 Longest Increasing Subsequence(LIS) 라는 유명한 문제라고 한다. A[n]에 수열을 넣고, d[n] : n까지의 가장 긴 증가하는 부분 수열의 길이. 여기서 d[n]은 A[n]을 포함해야 한다. d[1]은 1까지의 가장 긴 증가하는 부분 수열의 길이이다. A[1]밖에 없으므로 D[1]은 그냥 ..

https://www.acmicpc.net/problem/9465 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티 www.acmicpc.net 스티커를 때어내면, 그 스티커와 변을 공유하는 스티커들도 때어진다. 즉 때어낸 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커들은 사용할 수 없다. 이때 때어낼 수 있는 스티커 점수의 최대값을 구하는 문제. 일단 d[n]을 d[n] : 길이가 n인 스티커에서의 점수의 최댓값이라고 하자. 전의 포도주 문제와 비슷하게 n번째 열 일 때의 상태는 다음과 같이 있을 수 있다 0: 둘 다 떼어내지 않음 1 ..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 최대로 마실 수 있는 포도주의 양을 구해야 한다. 각 포도주잔에 포도주가 얼마나 있는지 나와있고 연속으로 3잔을 마실수는 없다. Solution 1차원 다이나믹 d[n] : n번째 잔 까지 최대로 마실수 있는 포도주의 양 a[n] : n번째 잔에 들어있는 포도주의 양 두 번째 인덱스를 "n번째 잔에서 연속으로 마신 잔의 수" 라고 하면 d[n][0] : n번째 잔을 마시지 않는다 d[n][1] : ..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수� www.acmicpc.net 오르막 수는 수의 자리가 오름차순을 이루는 수. 인접한 수가 같아도 오름차순으로 친다. 그리고 이 문제는 0으로 시작할수 있다. n = 1 일때 0 1 2 ... 9 n = 2 일때 01, 02, ... 09 // 9개 12, 13, ... 19 // 8개 23, 24, ... 29 // 7개 ... 89 // 1개 나는 이차원 배열의 첫번 째 인덱스를 수의 ..