Hailey

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net | 문제 해결방법 이 문제는 백준의 DP문제인 2579번_계단 오르기 문제와 거의 동일하다. 고려해야할 조건은 3번 연속으로 포도주를 마시면 안되는 것으로 계단 오르기 문제와 동일하고, 이 문제에서 추가해준 조건은 해당 위치의 포도주를 마신 경우와 마시지 않은 경우의 포도주량을 비교해 더 큰 값을 메모제이션 해주는 것이다. 계단오르기는 수의 크기가 오름차순으로 이루어져 있었기 때문에 이를 고려해줄 ..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net | 문제 해결방법 2차원 배열에서 목표지점까지 갈 수 있는 경로의 개수를 구하는 문제이다. 관련 알고리즘 : DFS + DP 핵심 아이디어는 방문했던 길을 한번 더 방문하지 않는 것 방문하지 않은 길을 한번 탐색하면, 결과는 두 가지가 나올 수 있다. 1. goal까지 갈 수 있는 경우 2. 사방으로 더이상 갈 길이 없는 경우 알고리즘 순서 1. 처음에 2차원 dp배열을 만든 후 -1로 초기화 해준다 ..

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 이 문제는 백준 11053번 가장 긴 증가하는 부분 수열을 풀고 for문 조건만 수정해서 제출했다. 11053_가장 긴 증가하는 부분 수열 해설법 https://hailey-v.tistory.com/9 [JAVA]백준 11053번: 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/110..

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관련 문제들만 찾아서 풀고 있다. 오늘은 그 중에서 '11053_가장 긴 증가하는 부분 수열'과 '11722_가장 긴 감소하는 부분 수열' 두 문제를 풀어보았다. | 문제 해결방법 관련 알고리즘 : 최장 증가 부분 수열(LIS) + DP 주어진 요소들 중에서 조건에 맞..