728x90 다이나믹 프로그래밍35 [JAVA]백준 1520번: 내리막 길 www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. 문제 설명 지도가 있을 때 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 문제이다. list 배열로 지도를 입력받고 list 배열과 같은 크기의 cache 배열을 만들고 -1로 채운다. -1로 채우는 이유는 현재 위치를 방문했는지 방문하지 않았는지 구분하기 위해서이다. 그 후 재귀를 통해 현재 위치와 각각의 상, 하, 좌, 우 list 값을 비교해 다.. 2021. 1. 16. [JAVA]백준 5557번: 1학년 www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 1. 문제 설명 숫자가 주어질 때 +,-만 사용하여 만들 수 있는 올바른 등식의 수를 구하는 문제이다. 재귀함수와 for문을 이용하여 풀었다. 1) 재귀 함수 점화식 x가 인덱스 번호, y가 현재까지 합이라고 한다면 cache[x][y]=cache[x+1][y+list[x+1]]+cache[x+1][y-list[x+1]] 이다. 2) for문 점화식 x가 현재 인덱스 번호, y가 인덱스 x-1까지의 합이.. 2021. 1. 16. [JAVA]백준 2225번: 합분해 www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1. 문제 설명 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 세는 문제이다. Top down 방식과 Bottom up 두 가지 방식으로 풀 수 있다. 1) Top down 변수 remain을 남은 합, k_use를 현재까지 더한 정수의 개수라고 한다면 cache [remain][k_use]=cache [remain-1][k_use]+cache [remain][k_use-1]이다. 점화식을 이용하여 위의 식을 얻을 수 있다. cache [remain][k_use]= ∑cache [remain-x][k_use-1] (0 2021. 1. 15. [JAVA]백준 11054번: 가장 긴 바이토닉 부분 수열 www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 1. 문제 설명 가장 긴 바이 토닉 수열의 길이를 구하는 문제이다. 바이 토닉 수열은 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1... > Sn을 만족하는 수열을 말한다. 가장 긴 증가하는 부분수열 문제를 풀었다면 어렵지 않게 해결할 수 있다. 왼쪽에서 시작해서 증가하는 부분 수열 문제를 풀고 오른쪽 끝에서 시작하여 증가하는 부분 수열 문제를 풀고 두 문제를 합쳐서 제일 긴 바이토닉 수열의 .. 2021. 1. 12. 이전 1 ··· 5 6 7 8 9 다음 728x90
