가장 긴 증가하는 부분 수열
가장 긴 증가하는 부분 수열 백준 11053번 문제 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 1. 문제 2. 풀이 2.1 풀이 방법 주어진 수열에서 길이 1부터 N까지 끝의 수가 n일 때, 가장 긴 증가하는 부분 수열을 구한다고 해보자. 즉, d[N] = N길이의 수열에서 마지막 값이 n일 때 가장 긴 증가하는 부분 수열 이된다. ※ 부분수열을 구하는 것이기 ..
2023. 1. 16.
내리막-길
내리막-길 백준 1520번 문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. 문제 2. 풀이 2.1 풀이 방법 d(i, j) 를 시작점에서부터 i, j로 갈 수 있는 경우의 수를 의미한다고 하자. 그러면 다음과 같은 점화식이 성립한다. d(i, j) = SUM(d(i - 1, j), d(i, j + 1), d(i + 1, j), d(i, j - 1)) (단, (i,j)의 높이보다 높을 경우만 더해준다.) 따라서 도착점을 (i, j)라고 할 ..
2022. 9. 8.
