본문 바로가기

동적계획법6

백준11053 가장 긴 증가하는 부분수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 점화식은 for를 돌면서 본인보다 이전에 나온 수의 크기가 더 작으면 그수에 1 증가 한 수를 dp에 저장하는 방법으로 해결했다. 이런 식으로 해결하면 현재값이 나온 수들 중 가장 큰 값이라면 이전까지 나온 수들 중 가장 큰 dp값에 1을 더하게 된다. if(arr[j] 2020. 5. 8.
백준 2156 포도주시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 동적계획법에 좀 익숙해지나 했는데.... 여전히 어렵다. 꼭 동적계획법 유형의 문제는 다시한번 혼자힘으로 다시 풀어보아야 겠다. 계단.. 2020. 5. 5.
백준10844 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 드디어 혼자 힘으로 동적계획법 문제를 풀었다. 처음에는 고민을 해도 문제가 풀리지 않았는데 3학년1학기때 보았던 동적계획법 강의를 조금 보고 Bottom-Up 개념을 다시 확실히하고 문제를 보니 어떤 방식으로 풀어야 할 지 생각이 났다. 먼저 2차원 배열을 통해 문제를 풀어야했는데 행의 크기는 0부터 9까지 10개의 자리를 할당해도 되지만 배열 인덱스오류를 방지하기위해 12개 자리를 할당했다. 열의 크기는 N+1만큼 자리를 주었다. 이 문제를 해결할 때 사용되는 일반적인 경우는 현재 값보다 한 자릿 수가 큰 부.. 2020. 5. 4.
백준 1149 RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다. www.acmicpc.net DP문제가 익숙하지않아서 정말 오랜시간 고민했다. 결국 스스로 해결하지 못하고 다른 블로그를 참고하여 문제를 해결했다. 이 문제를 계기로 동적계획법을 푸는데 2차원 배열을 이용하여 풀 수 있다는 방법도 알게되었다. 하나의 값만 저장하여 해결하는 것만 생각해서 답이 떠오르지 않았던 것이다. 이 문제의 경우 하나의 값만 저장하게 되면 지금 선택하지 못하는 색에 .. 2020. 4. 28.

티스토리툴바