분류 전체보기

[백준] 점프 점프 (11060번 JAVA) / DP [접근 방법] arr 배열로 Ai 배열을 입력 받는다. DP 배열은 현재 위치 까지 이동하는데 소요된 "최소 점프 수" 이다. 현재 위치인 2에서 점프 가능한 칸 수가 3인 경우, 3, 4, 5으로 이동가능 하다. 따라서, DP[3], DP[4], DP[5] 값은 "DP[2] + 1" 으로 갱신 된다. arr[3] = 2 이므로, 4, 5로 이동 가능하다. 이때, 기존 DP[4] 와 DP[5]에 값이 존재하므로, 기존 DP[4] = 2의 경우 (1 -> 2 -> 4) 와 (1 -> 2 -> 3 -> 4)의 경우 중 점프 횟수가 더 작은 값으로 갱신 한다. 완성된 DP는 다음과 같다. [JAVA 코드] // 11060 - 점프 점프 import java..

[백준] BOJ 거리 (12026번 JAVA) / DP [접근 방법] 스타트는 항상 B 이다. B - > O - > J 순으로 이동하여야 한다. DP 배열의 의미는 해당 위치 까지 "이동하는데 든 에너지의 최솟값" 이다, 현재 위치의 문자가 B 라면, 다음 이동 가능한 문자인 O에 대하여, 현재 위치의 문자가 O 라면, 다음 이동 가능한 문자인 J에 대하여, 현재 위치의 문자가 J 라면, 다음 이동 가능한 문자인 B에 대하여, 탐색하여 가장 적은 에너지를 소모하는 것을 DP에 저장한다. 1

[백준] 점프 (!) (1890번 JAVA) / DP [ 접근 방법 ] 게임 판에 적혀있는 '이동 가능 거리' 를 arr 2차원 배열에 저장 해당 좌표까지 도착 할 수 있는 방법 수 를 DP 2차원 배열에 저장 좌표 (1, 1) 부터 (N, N) 까지 DP 시작 한다. 예제로 설명한다면, [입력값] [DP 출력] DP의 (1,1)을 초기값으로 1로 설정한다. (1, 1)에서 '이동 가능 거리'는 ' 2 ' 이다. (1, 1) -> (3, 1) (1, 1) -> (1, 3) 으로 이동 가능하다. 이와 같은 방법으로 한다면, 위와 같은 DP 출력 값이 나오게 된다. [ JAVA 코드 ] // 1890번 점프 import java.util.*; import java.io.*; class Main { publi..

[백준] 퇴사 (!) (14501번 JAVA) / DP [접근 방법] * 물리적으로 불가능한 것 (퇴사 후엔 상담이 불가능) 을 제외한다. (N = 7인 경우, 7일차에 2일이 걸리는 상담을 할 수 없다.) 역방향으로 DP를 도출한다. N -> 1 순으로, for (i = N -> 1 까지 i--){ // 물리적으로 불가능한 것 제외 if ( 현재 일자(i) + 상담에 드는 기간(T[i]) > N + 1 ){ DP[i] = DP[i+1]; } else { i 날짜의 일을 하는 경우 => DP[i + T[i]] + P[i] i 날짜의 일을 하지 않는 경우 => DP[i+1] 중 최댓값 구하기 } } [JAVA 코드] // 14501 - 퇴사 import java.util.*; import java.io.*..

[백준] 연속합 2 (!) (1932번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습) [접근 방법] 첫번째 방법 ) DP를 1차원 배열로 2가지 구성 Left -> Right (index : 0 -> n-1) 방향으로 연속합 DP1 배열 을 구성 Right -> Left (index : n-1 -> 0) 방향으로 연속합 DP2 배열 을 구성 index : i 의 원소를 제외하는 경우의 연속합 최댓값을 갱신하며 구한다. i 번째 원소를 제외한 연속합 = DP1[i-1] + DP2[i+1] 두번째 방법 ) DP를 2차원 배열로 구성 [JAVA 코드 - 첫번째 방법] import java.io.BufferedReader; import java.io.BufferedWriter; import java...

[백준] 가장 긴 바이토닉 부분 수열 (11054번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습) [접근 방법] 1. LIS를 구한다. 2. LDS를 구한다. 3. LIS + LDS - 1를 하여 가장 긴 바이토닉 부분 수열 DP를 구한다. [JAVA 코드] import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main{ public static void main(String[] args) throws IOE..