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/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 문제만 이해하면 해결방법은 단순한 조합문제로 아주 쉬운 문제이다. 조합의 식을 nCr 이라고 할 때, 강 동쪽을 n 강 서쪽을 r로 생각하면 된다. 동쪽에서 r개의 사이트를 고르는 경우의 수(순서가 없고 중복도 없다.) r개의 조합을 고르면, 서쪽 사이트와 순서대로 선을 그으면 되기 때문에 겹칠 일이 없다. 따라서, 우리는 0< N, M