목록백준 (183)
Study hard
https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 두 개의 dp배열이 필요하다. 하나는 각각 숫자들의 앞에서 증가 수열의 길이를 저장하는 dp_front, 다른 하나는 각각 숫자들의 뒤에서 감소 수열의 길이를 저장하는 dp_back으로 했다. dp_front[i] : i를 마지막 숫자로 했을 때 가장 긴 증가 부분 수열 dp_back[i] : i를 시작 숫자로 했을 때 가장 긴 감소 부분 수열 모두 구하고, 인덱스마다 dp_front[x] + dp_back[x] -..
https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} � www.acmicpc.net 2020/06/09 - [백준/DP] - (c++)백준 11053번: 가장 긴 증가하는 부분 수열 위 문제와 거의 똑같다. 부등호 하나만 바꿔주면 된다. #include using namespace std; int N; int A[1001]; long long dp[1001]; void DP() { long long M..
https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net 이 문제는 앞에서부터 dp배열을 채웠다. 가장 긴 증가하는 수열문제와 비슷하게 현재 인덱스보다 앞부분을 보면서 값이 더 작고 dp가 제일 큰 것을 저장한 후, 현재 dp에 더하면 된다. 2020/06/09 - [백준/DP] - (c++)백준 11053번: 가장 긴 증가하는 부분 수열 #include using namespace std; ..
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 이번에도 dp배열을 뒤에서부터 쌓았다. (앞에서부터 쌓아도 된다.) ※점화식※ dp[i] : i를 수열의 첫번째 숫자로 했을 때 증가하는 수열의 최대 길이 dp[1~N] 1로 초기화 i=N-1부터 시작하여 1이 될때까지 진행하고, 2중 for문으로 j=i+1부터 N번째 값까지 i번째 값과 비교해서 i번째 값보다 크다면 ..
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 앞에서 포도주를 마셨는지 안마셨는지가 뒤에 포도주를 마실 수 있는지에 영향을 주므로, 해당 순서 포도주를 마셨을 때의 최대 포도주의 양과 마시지 않았을 때의 양을 따로 계산해 주었다.(2차원 배열) ※점화식※ dp[i][0] : (앞에서부터) i번째 포도주를 마시지 않기로 했을 때 지금까지 마신 포도주의 최대 양 dp[i][1] : (앞에서부터) i번째 포도주를 마시기로 했을 때 지금까지 마신 포도..
https://www.acmicpc.net/problem/9465 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티 www.acmicpc.net 만약 처음에 (1,1)위치의 스티커를 고르면 다음 스티커로 (2,2)위치의 스티커를 고를지, (2,3)위치의 스티커를 고를지 골라야 한다. ∵(2,2)위치의 스티커를 고르면 (2,3)위치의 스티거를 고를 수 없게 되므로 더 큰 점수를 갖는 스티커를 고르는 게 유리! v ? ? (1,3)위치의 스티커는 여기서 고려하지 않아도 된다. 만약 (1,3)을 선택할 거라면 (2,2)를 이미 선택했어야 최대가 될..