Dev.baelanche

피보나치 수열과 비슷한 규칙을 가진 수열이다. 수열을 잘 살펴보면 dp[i] = dp[i-3] + dp[i-2] 와 같은 점화식을 얻을 수 있다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long dp[] = new long[101]; dp[0] = 0; dp[1] = dp[2] = 1; for(int i=3; i0) { int n = sc.nextInt(); System.out.println(dp[n]); } } }

N일 마다 벌 수 있는 최대 이익을 저장하면서 진행한다. dp[i] = a[i][1]; //상담 이익 dp배열의 초기값은 상담 이익으로 했다. 예제의 예를 들면 1일 2일 3일 4일 5일 6일 7일 Ti 3 5 1 1 2 4 2 Pi 10 20 10 20 15 40 200 Pi 의 값을 모두 넣어준 셈인데 6일, 7일에 주어진 일은 완료할 수가 없다. 이에 대한 예외처리는 마지막에 해주었다. 1일부터 진행하며 그 날 주어진 상담을 완료할 수 있으면 dp 값을 올려준다. n번째날의 일을 수행하여 n+1번째날의 일을 수행하지 못하면 손해가 될 수 있으므로 dp값을 업데이트 할때는 기존의 값과 비교하여 큰 값으로 갱신해주어야 한다. if(i - j >= a[j][0]) dp[i] = max(dp[j] + a[..

메모이제이션 + 탐색을 요구하는 문제다. 1. 경로의 개수가 21억즈음이므로 메모이제이션 없이 돌리면 시간초과가 난다. 2. 아래, 오른쪽으로 가는 경로의 개수를 합하면서 이동하기 때문에 dp 배열은 long으로 해줘야 한다. 3. 게임판 배열은 0

각 다리의 수에 따른 경우의 수를 이용하여 풀어야 한다. n / m 1 2 3 4 5 6 1 1 2 3 4 5 6 2 X 1 3 6 10 15 3 X X 1 4 10 20 n이 1일땐 m의 수만큼 경우의 수가 증가한다. n이 2일땐 m이 증가함에 따라 dp[n][m] = dp[n][m-1] + dp[n-1][m-1] 의 형식으로 증가하는걸 볼 수 있다. n이 3일때도 마찬가지이다. n이 1일때의 초기값과 n == m 일때의 초기값을 배열에 대입해주고 위 점화식을 이용하여 풀면된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long dp[][] = new long[30][3..

n 이 1일때 9 (1, 2, 3, 4, ..., 9) n 이 2일때 17 이다. 십의 자리수가 5일때 54 혹은 56 이어야 하므로 자리수 n 이 i, 일의 자리수가 j 일때 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]; 위와 같은 점화식을 얻을 수 있다. n이 2일때의 계단수가 17인 이유는 01 이 빠졌기 때문이다. 일의 자리수가 0일때는 제외해야 하므로 점화식에 추가해준다. if(j == 0) dp[i][j] = dp[i-1][j+1]; else dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]; 마찬가지로 9일때도 90 같은 수는 만들 수 없으니 예외처리 한다. if(j == 0) dp[i][j] = dp[i-1][j+1]; else if(j == 9..

수열의 크기와 같은 크기의 dp 배열을 만들어 각 인덱스별로 최대값을 저장한다. 수열의 값 중 적어도 한 개를 선택해야 하고 연속적으로 사용해야 하므로, 이전 dp의 최대값 + 현재 배열의 값 / 현재 배열의 값을 비교하여 큰 것을 사용하면 된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a[] = new int[n]; int dp[] = new int[n]; for(int i=0; i

길이가 1일때 10(1+1+1+1+...+1) 길이가 2일때 55(1+2+3+4+...+10) 길이가 3일때 220(1+3+6+10+...+55) 이다. dp[2][1] = dp[1][1] dp[2][2] = dp[1][1] + dp[1][2] dp[2][3] = dp[1][1] + dp[1][2] + dp[1][3] ...... 을 바탕으로 점화식을 세워 풀이한다. 각 인덱스를 더하면 자료형의 범위를 초과할 수 있으므로 매 연산마다 10007 로 나누어주고 마지막에도 나누어주면 되겠다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); in..

수열은 자주 나오는 DP 문제이다. 이곳에서 LCS에 대한 설명을 확인할 수 있다. 위에서 나온 설명대로 점화식을 구현하여 풀었다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String a = " " + sc.next(); String b = " " + sc.next(); int dp[][] = new int[b.length()][a.length()]; for(int i=1; i