Hailey

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net | 문제 해결방법 관련 알고리즘 : DP 규칙 찾기 나의 풀이 방법은 n이 홀수인 경우와 짝수인 경우를 나누어 계산한다. n=1인 경우는 단 한 가지 n=2인 경우는 세 가지 n=3인 경우 n이 홀수일 경우의 규칙은 바로 전에 구한, n=2일때의 타일들에 맨 앞, 맨 뒤에 하나의 타일을 붙여주는 것이다. 이 경우 2x1 타일로만 이루어진 경우가 중복해서 나오기 때문에 -1을 해준다. f(3) = f(2) * 2 - 1 n=4인..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net | 문제 해결방법 이 문제를 푸는데 약 두 시간이 걸렸다. 최대한 힌트를 참고하지 않고 풀어보려고 노력했더니 더 공부가 많이 되었다. 그리고 DP문제는 어떤 값을 메모제이션 할 것인지를 결정하는 것이 굉장히 중요한 것 같다. 1. 첫 번째로 고려할 점 처음에는 dp배열에 계단수의 시작되는 수가 index인 위치에 각 경우의 수를 넣어주었다. f(1) 인 경우, 0으로 시작되는 수만 제외하면 1부터 9까지 각각 자신의 수로 수를 만들 수 있다. 그래서 경우의 수는 f(1) 0 1 2 3 4 5 6 7 8 9 0 ..

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 주어진 요소들 중에서 조건에 맞..