목록전체 글 (217)
Study hard
![](http://i1.daumcdn.net/thumb/C150x150.fwebp.q85/?fname=https://blog.kakaocdn.net/dn/CEPlj/btqEIVfjSkB/qFFJzrwCwzbHLjoTlejFz0/img.jpg)
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; ..
![](http://i1.daumcdn.net/thumb/C150x150.fwebp.q85/?fname=https://blog.kakaocdn.net/dn/brs4J9/btqEHOH0vpj/LxuU6GQkwKJ9UIjpXusbCk/img.jpg)
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번째 값보다 크다면 ..
![](http://i1.daumcdn.net/thumb/C150x150.fwebp.q85/?fname=https://blog.kakaocdn.net/dn/bOto2n/btqEJinHKyC/9oITfAU00nhM4JJc6jFUh0/img.jpg)
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 앞에서 포도주를 마셨는지 안마셨는지가 뒤에 포도주를 마실 수 있는지에 영향을 주므로, 해당 순서 포도주를 마셨을 때의 최대 포도주의 양과 마시지 않았을 때의 양을 따로 계산해 주었다.(2차원 배열) ※점화식※ dp[i][0] : (앞에서부터) i번째 포도주를 마시지 않기로 했을 때 지금까지 마신 포도주의 최대 양 dp[i][1] : (앞에서부터) i번째 포도주를 마시기로 했을 때 지금까지 마신 포도..
![](http://i1.daumcdn.net/thumb/C150x150.fwebp.q85/?fname=https://blog.kakaocdn.net/dn/c6vAt4/btqEG9eAZ8K/K26VHW5bR1BKylAxnTdTUK/img.jpg)
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)를 이미 선택했어야 최대가 될..
![](http://i1.daumcdn.net/thumb/C150x150.fwebp.q85/?fname=https://blog.kakaocdn.net/dn/bECqY0/btqEHaqAjCx/7pg2f5qo3WJzMmiGkc6w7K/img.jpg)
https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 1. 0은 첫번째 자리에 올 수 없다. 2. 1은 앞에 0이 있어야 나올 수 있다. ※점화식※ dp[i][j] : i번째 자리가 j일 때 이친수 개수 dp[1][0] = 0 (첫번째 자리에 0 올 수 없다.) dp[1][1] = 1 dp[x][0] = dp[x-1][0] + dp[x-1][1] (x번째 자리에 0이 오면 그 앞은 0과 1 모두 있을 수 있다.) dp[x][1] = dp[..
![](http://i1.daumcdn.net/thumb/C150x150.fwebp.q85/?fname=https://blog.kakaocdn.net/dn/tphhV/btqEG9SDnYL/kQuneqOZefb17ajhiUkpDK/img.jpg)
https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수� www.acmicpc.net 뒤에 오는 숫자를 신경써야 한다. 9 다음의 수는 9밖에 올 수 없다. ※점화식※ dp[i][j] : i번째 자리에 j가 올 때 경우의 수 ※i=N부터, j=9부터 점화식 따라가기 if(j==9) dp[i][j] = dp[i+1][j] (j가 9이면 다음 숫자는 9밖에 못 온다.) else dp[i][j] = dp[i][j+1] + dp[i+1][j] (9가 ..