⬛ 11. DP 동적 계획법
⬛ DP 접근 방식
- 점화식의 규칙성이 존재해야 한다.
- 점화식 세우기 : D[i] 배열의 제대로 된 정의
- 점화식을 이용하여 D[i] 배열 채우기
- D[N] 을 출력하면 == 정답이어야 한다.
⬛ 메모이제이션의 이해
앞선 부분 문제 푼 결과를 DP 테이블에 저장해둔 뒤, 재사용 할 것
- 톱 다운 방식 : 주로 재귀함수
: 큰 문제부터 점차 작은 문제로
- 바텀-업 방식 : 주로 반복문
: 작은 문제부터 큰 문제로 확장
⬛ 0-1 배낭 문제
- 0-1 배낭 문제 : 물건을 통째로 배낭에 넣는데, 담을 수 있는 한 ‘최대 가치 낳도록 담는 문제
- 풀어볼 문제 : 동전 1, 동전 2, 평범한 배낭문제 등.
🟦 백준 4781번. 사탕 가게 | DP- 배당문제 (냅색)
문제
상근이는 선영이와 걸어가다가 사탕 가게를 지나가게 되었다. 갑자기 상근이는 선영이에게 사탕이 얼마나 건강에 안 좋은지 설명하기 시작했다. 선영이는 매우 짜증이 났고, 상근이에게 누가 더 건강이 안 좋아질 수 있는지 내기를 하자고 했다. 상근이는 내기를 그 즉시 받아들였다.
두 사람은 같은 돈을 가지고 가게에 들어가서 사탕을 산다. 이때, 구매한 사탕의 칼로리가 더 큰 사람이 내기에서 이기게 된다.
상근이는 잠시 화장실에 갔다온다고 핑계를 댄 뒤에, 노트북을 열고 사탕 가게의 시스템을 해킹하기 시작했다. 이 시스템에는 현재 사탕 가게에 있는 사탕의 가격과 칼로리가 모두 등재되어 있다. 각 사탕의 개수는 매우 많기 때문에, 원하는 만큼 사탕을 구매할 수 있다. 또, 사탕은 쪼갤 수 없기 때문에, 일부만 구매할 수 없다.
사탕 가게에 있는 모든 사탕의 가격과 칼로리가 주어졌을 때, 어떻게 하면 칼로리의 합이 가장 크게 되는지를 구하는 프로그램을 작성하시오.
입력
각 테스트 케이스의 첫째 줄에는 가게에 있는 사탕 종류의 수 n과 상근이가 가지고 있는 돈의 양 m이 주어진다. (1 ≤ n ≤ 5,000, 0.01 ≤ m ≤ 100.00) m은 항상 소수점 둘째자리까지 주어진다.
다음 n개 줄에는 각 사탕의 칼로리 c와 가격 p가 주어진다. (1 ≤ c ≤ 5,000, 0.01 ≤ p ≤ 100.00) c는 항상 정수, p는 항상 소수점 둘째자리이다.
입력의 마지막 줄에는 '0 0.00'이 주어진다.
출력
각 테스트 케이스에 대해서, 상근이가 돈 m을 가지고 구매할 수 있는 가장 높은 칼로리를 출력한다.
풀이
- 일단 소수점은 X100을 해서 Math.round()로 반올림 한 뒤 int로 받을 것.
- D[i]의 정의 : i원을 사용하여 얻을 수 있는 최대 칼로리
- dy[j] = Math.max(dy[j], dy[j-p] + c ) ;
- 그냥 j원으로 살 때 vs j-p원+p원 조합으로 살때 중 더 큰 칼로리로 세팅한다.
import java.util.Scanner;
/*배군 4781번. 사탕 가게 -
* 냅색(배낭) 문제 - 동전1, 동전2 , 평범한 배낭 등
* D[i] 의 정의 : i원을 가지고 얻을 수 있는 최대 칼로리.
* */
//4781번. 사탕 가게 문제 복습
public class Main {
//실행 메인
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb= new Scanner(System.in);
while(true) {
int n = kb.nextInt();
int m = (int) Math.round(kb.nextDouble() * 100);
if(n == 0 && m ==0) break;
int[] dy = new int[m+1];
for(int i=0; i<n; i++) {
//사탕 칼로리, 가격 입력받기
int c = kb.nextInt(); //얘가 칼로리
int p = (int) Math.round(kb.nextDouble() * 100); //얘가 돈
for(int j =p; j<=m; j++) {
dy[j] = Math.max(dy[j], dy[j-p] + c);
//그냥 j원으로 살 때 vs j-p원+p원 조합으로 살때 중 더 큰 칼로리로 세팅한다.
}
}
System.out.println(dy[m]);//m원으로 살 수 있는 애
}
}
}🟦 백준 2073번. 수도 배관 공사
문제
아기염소들이 언덕에서 풀을 뜯고 놀다 보면 항상 도중에 목이 마르곤 했다. 그들은 불편함을 참지 못하고 수도관을 설치하여 거리 D(7 ≤ D ≤ 100,000)만큼 떨어진 곳의 강에서 물을 끌어오기로 했다. 근처의 인간 마을에서 P개(1 ≤ P ≤ 350)의 파이프를 매입했는데, 각각은 길이 Li와 용량 Ci로 나타낼 수 있다. (Li와 Ci는 모두 223보다 작거나 같은 양의 정수이다)
파이프들은 일렬로 이어서 수도관 하나로 만들 수 있으며, 이때 수도관의 용량은 그것을 이루는 파이프들의 용량 중 최솟값이 되고, 수도관의 길이는 파이프들 길이의 총합이다.
수도관을 한 개 만들어 총 길이가 정확히 D와 같게 할 때, 가능한 최대 수도관 용량을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 D와 P가 주어진다. 두 번째 줄부터 P개의 줄이 차례로 주어지고, 각 줄마다 Li와 Ci가 주어진다. 길이 합이 D가 되게 하는 수도관의 부분집합이 적어도 하나 존재한다.
출력
가능한 최대 수도관 용량을 첫째 줄에 출력한다.
풀이
- 이 문제는 파이프가 각각 1 개씩만 존재하기 때문에 주의해야 한다.
- 중복해서 사용해서는 안된다.
- D[i]의 정의 : i길이로 만들 수 있는 최대 용량
- 용량은 i길이를 만들 수 있는 두 파이프의 용량 중 작은 값이어야 한다.
- 따라서, 기존 값보다는 큰 용량이면서 만들 수 있는 조합의 용량 중에선 min 값으로 dy[] 값을 세팅해야 한다.
package to_0725_4;
import java.util.Scanner;
/*2073번. 수도배관 공사
* 기존 용량보다 크면서도, 두 파이프의 조합(중 작은 용량)의 값으로 세팅
* */
public class Main {
//실행 메인
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb= new Scanner(System.in);
int D = kb.nextInt();
int P = kb.nextInt();
int[] dy = new int[D+1];
for(int i=0; i<P; i++) {
int L = kb.nextInt();//길이값
int C = kb.nextInt(); //용량값
for(int j=D; j>=L; j--) {//역으로 돌아야 파이프 중복X(하나씩만 있기때문)
if(dy[j-L] == 0) continue;//넘어감
dy[j] = Math.max(dy[j], Math.min(dy[j-L], C));
//기존 값보다는 크면서, 만들 수 있는 두 파이프의 조합 중 작은 용량값으로 업데이트
}
dy[L] = Math.max(dy[L], C);//기존 값보다 큰 용량으로 세팅
}
System.out.println(dy[D]);//최종 답 출력
}
}
🟦 백준 2579번. 계단 오르기
문제
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.
예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.
계단 오르는 데는 다음과 같은 규칙이 있다.
- 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
- 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
- 마지막 도착 계단은 반드시 밟아야 한다.
따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.
각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.
입력
입력의 첫째 줄에 계단의 개수가 주어진다.
둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.
출력
첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.
풀이
D[i] 정의 : 시작~i번째 계단 밟았을 때의 최대 점수
- 항상 i번째가 마지막 계단이라고 생각해보자.
- i번째를 마지막으로 반드시 밟으려면 이 직전에 선택할 수 있는 계단은 2가지이다.
1) 바로 직전 계단 밟고 → 현재 계단 밟는 경우
- 이 경우에도, 3 계단을 연달아 밟아서는 안되므로
D[i-3] + score[i-1] + score[i] 가 될 것이다.
즉, 3계단 전에서 → 직전 계단 밟고, → 현재 계단까지 이른 것이다.
2) 두 계단 전 밟고 → 현재 계단 밟는 경우
D[i-2] + score[i] 가 될 것이다.
따라서 아래와 같이 코드가 짜인다.
D[i] = Math.max(D[i-2] + score[i], D[i-3] + score[i-1] + score[i] );
전체 코드
package to_0725_5;
import java.util.Scanner;
/*2579번. 계단 오르기 */
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb= new Scanner(System.in);
int N = kb.nextInt();//계단 개수
int[] score = new int[N+1];
for(int i=1; i<=N; i++) score[i] = kb.nextInt();
int[] D = new int[N+1];
D[1] = score[1];
if(N > 1) D[2] = score[1] + score[2];
for(int i=3; i<=N; i++) {
D[i] = Math.max(D[i-2] + score[i], D[i-3] + score[i-1]+ score[i]);
}
System.out.println(D[N]);
}
}
🟦 백준 1994번. 등차수열
문제
N개의 음 아닌 정수들이 있다. 이들 중 몇 개의 정수를 선택하여 나열하면 등차수열을 만들 수 있다. 예를 들어 4, 3, 1, 5, 7이 있을 때 1, 3, 5, 7을 선택하여 나열하면 등차수열이 된다. 이와 같이 했을 때, 등차수열의 길이가 최대 얼마까지 가능한지 알아내시오.
등차수열은 일정한 값만큼 증가하는 수열을 말한다. 이 일정한 값은 음수나 0도 될 수 있다.
입력
첫째 줄에는 숫자의 개수 N(1 ≤ N ≤ 2,000)이 주어지고, 다음 N개의 줄에는 정수들이 주어진다. 정수들은 1,000,000,000보다 작은 음이 아닌 정수이다.
출력
첫째 줄에 가장 긴 등차수열의 길이를 출력한다.
풀이
- 우선 nums[] 정렬 시키고, i<j 인 순서 유지
- D[i][j] : i번째 수, j번쨰 수를 마지막 두 항으로 하는 등차수열의 최대 길이
- 공차 : nums[j]-num[i]
- pre 값을 찾는다. pre값은 i번쨰 수의 앞에 존재하는 등차 항의 값으로, nums[i] - (공차) 값이 존재할 경우 해당 값을 갖는 k번째 값 ~ i번쨰 값의 등차 길이에 현재 j번쨰 수까지를 포함하는 +1 처리를 하여 더 큰 길이로 값을 세팅한다.
- answer는 기존 값보다 큰 최대 길이 등장하면 갱신
import java.util.Arrays;
import java.util.Scanner;
/*1994번. 등차수열 */
public class Main {
//solution 함수
public int solution(int n, int[] nums) {
int answer = 0;
if(n==1) return 1;
int[][] dy = new int[n+1][n+1];
//정렬
Arrays.sort(nums);
//
for(int i=1; i<n; i++) {
for(int j=i+1; j<=n; j++) {
dy[i][j] = 2;//일단 기본 2 세팅
//i 앞의 항 찾는 거임 따라서 i번쨰 값에서 (공차)를 빼주면 되는 건데
int pre = nums[i] - (nums[j] - nums[i]); // 2 * nums[i] - nums[j]
int k =0;//o초기화 해준뒤
for(k =i-1; k>=1; k--) {//i앞~1까지 역순으로 돌면서 k 즉, 앞의 등차수열 항 존재하는지 탐색
if(nums[k] == pre) break;//탈출
}
//i,j번쨰를 마지막으로 하는 등차의 최대 길이 = 기존 vs k~i까지의 길이 + 1
dy[i][j] = Math.max(dy[i][j], dy[k][i] + 1);
answer = Math.max(answer, dy[i][j]); //기존값보다 큰 길이 생기면 갱신
}
}
return answer;
}
//실행 메인
public static void main(String[] args) {
// TODO Auto-generated method stub
Main T = new Main();
Scanner kb= new Scanner(System.in);
int n = kb.nextInt();
int[] nums =new int[n+1];
for(int i=1; i<=n; i++) nums[i] = kb.nextInt();
System.out.print(T.solution(n, nums));
}
}
🟦 1과 2로 N을 만드는 방법의 수 구하기
- 입력 : N
- 출력 : 1과 2 조합으로 N을 만들 수 있는 방법의 수
- 현재 i번째를 마지막 계단이라고 생각하며 조합을 해보자.
- D[1] = 1 D[2] = 2 (1+1. 2) D[3] = 3 (1+1+1, 1+2, 2+1)
- D[4] = 5 즉, 규칙성이 보인다.
- D[i] 의 정의 : 1과 2의 조합으로 i를 만들 수 있는 방법의 수
- 점화식 : D[i] = D[i-1] + D[i-2]
/*1과 2로 N을 만들 수 있는 방법의 수 */
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb= new Scanner(System.in);
int N = kb.nextInt();
int[] D = new int[N+1];
D[1] = 1;
D[2] = 2;
for(int i=3; i<=N; i++) {
D[i] = D[i-1] + D[i-2];
}
System.out.println(D[N]);
}
}
🟦 돌다리 건너기
- 이 문제는 N개의 돌다리가 존재하면 시작점에서 ~끝점까지 도달하는 데 N개를 건너므로 N+1까지의 DP를 구해야 정답이 나온다.
- 점화식 : D[i] = D[i-1] + D[i-2]
- 따라서 N+2크기로 D[] 배열 선언하고, 앞 문제와 똑같이 규칙성을 따르되, 마지막 정답은 D[N+1] 로 출력
package to_0728_2;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb= new Scanner(System.in);
int N = kb.nextInt();
int[] D = new int[N+2];
D[1] = 1;
D[2] = 2;
for(int i=3; i<=N+1; i++) {
D[i] = D[i-1] + D[i-2];
}
System.out.println(D[N+1]); //N+1위치로 출력
}
}
🟦 LIS | 최대 부분 증가수열
설명
N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라.
예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어
길이가 5인 최대 부분 증가수열을 만들 수 있다.
입력
첫째 줄은 입력되는 데이터의 수 N(3≤N≤1,000, 자연수)를 의미하고,
둘째 줄은 N개의 입력데이터들이 주어진다.
출력
첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.
풀이
- dy[i] 정의 : i를 마지막 항으로 하는 최대 길이
- arr[i] 현재 값으로 찍은 값을 기준으로,
- j는 i 앞을 순회하면서, arr[i] 보다 작은 arr[j]를 가지면서, dy[j] 가 가장 큰 값을 찾아 dy[j] + 1 하여 현재의 dy[i] 값을 세팅한다.
import java.util.Scanner;
//최대부분 증가 수열
public class Main {
static int[] dy;
static int solution(int n, int[] arr) {
int answer = 0;
dy = new int[n];
dy[0] = 1;//길이 1 초기화
for(int i=1; i<n; i++) {
int max = 0;
//j로 i앞을 순회하면서 현재 i로 찍은 값보다 작은 arr[j] 이면서 dy[j]의 최대값에 +1처리 해줄 거임
for(int j=i-1; j>=0; j--) {
if(arr[i] > arr[j] && dy[j] > max) {
max = dy[j];
}
}
dy[i] = max+ 1;//가장 큰 값 +1 처리
answer = Math.max(answer, dy[i]);
}
return answer ;
}
//실행 메인
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb= new Scanner(System.in);
int N = kb.nextInt();
int[] arr = new int[N];
for(int i=0; i<N; i++) arr[i] = kb.nextInt();
System.out.println(solution(N, arr));
}
}🟦 최대점수 구하기 | 냅색 알고리즘
문제
이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩 니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)
▣ 입력설명
첫 번째 줄에 문제의 개수N(1<=N<=50)과 제한 시간 M(10<=M<=300)이 주어집니다. 두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.
▣ 출력설명
첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.
풀이
- D[i] 정의 : i분 동안 얻을 수 있는 최대 점수
- 우선, 한 유형당 한 개만 풀 수 있다고 제한이 있기 때문에, 문제를 중복해서 풀 수는 없다.
ex) 10점 짜리 문제를 5점+5점 이런 식으로 중복 X
- 역순으로 돌면서, D[j-T] + sc 의 값이 더 큰 값으로 세팅해야 한다.
package to_0728_6;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb= new Scanner(System.in);
int N = kb.nextInt();//문제 개수
int M = kb.nextInt(); //제한 시간
int[] dy = new int[M+1];//시간을 기준으로
for(int i=0; i<N; i++) {//문제 각각
int S = kb.nextInt();//점수
int T = kb.nextInt();//시간
for(int j=M; j>=T; j--) {//시간 역순으로 돌면서
dy[j] = Math.max(dy[j], dy[j-T] + S);//기존 시간 vs T시간과 조합한 점수 중 큰값 세팅
}
}
System.out.println(dy[M]);
}
}
🟦 동전 교환 | 냅색 알고리즘
- 입력 : N개의 동전 종류 주어지고, M원도 주어진다.
- 출력 : M원을 만드는 최소 동전의 개수 구하기
풀이
- D[i] 는 i원을 거스르는 최소 동전의 개수가 된다.
- D[] 배열을 우선 Integer.MAX_VALUE 값으로 초기화한다.
- 여러 개의 동전을 중복해서 사용 가능하므로 각 동전 종류 i에 대하여 j=i~M까지 순회하면서 거스를 수 있는 최소 동전 개수를 탐색한다.
package to_0728_8;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb= new Scanner(System.in);
int N = kb.nextInt(); //동전 종류
int[] arr = new int[N]; //동전 종류 받는 배열
for(int i=0; i<N; i++) arr[i] = kb.nextInt();
int M = kb.nextInt(); //총 N원
int[] dy = new int[M+1];//i원을 거스르는데 사용되는 최소 동전 개수
//일단 최댁값으로 채워넣기
Arrays.fill(dy, Integer.MAX_VALUE);
//그래도 dy[0] = 0세팅
dy[0]= 0;
for(int i=0; i<N; i++) {
int cur = arr[i];//현재 동전을 기준으로
for(int j=cur; j<=M; j++) { //현재 동전부터 M원까지 돌면서
dy[j] = Math.min(dy[j], dy[j-cur] + 1);
//기존 값보다 더 작은 개수 발견 시 갱신
}
}
System.out.println(dy[M]);
}
}
🟦 가장 높은 탑 쌓기 | DP & 그리디
문제
밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래 에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프 로그램을 작성하시오. (조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다. (조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다. (조건3) 벽돌들의 높이는 같을 수도 있다. (조건4) 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다. (조건5) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.
입력
입력 파일의 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높 이 그리고 무게가 차례대로 양의 정수로 주어진다. 각 벽돌은 입력되는 순서대로 1부터 연속 적인 번호를 가진다. 벽돌의 넓이, 높이 무게는 10,000보다 작거나 같은 자연수이다
출력
첫 번째 줄에 가장 높이 쌓을 수 있는 탑의 높이를 출력한다.
풀이
- dy[i] 정의 : i번째 벽돌을 가장 위로 하는 최대 탑의 높이
- 우선 Top이라는 벽돌 클래스 생성하고, 기본 정렬 기준을 밑면 내림차순 으로 고정시켜둔다.
- 입력값은 이제, 넓이 내림차순 상태이므로, 이 상태에서 dy[0] 값은 가장 첫번째 값의 h로 세팅해두고,
- for(int i=1 ~N) 순회하고 내부에는 for(int j=i-1~0) 역순 순회하며
- 현재 i로 찍은 뒷쪽 값의 w보다 무거운 j를 가지면서, dy[j]값이 가장 큰 앞쪽 값을 가져와 현재의 dy[i]값에 더하고 i의 h값도 함께 누적한다.
- answer는 dy[] 값 중 가장 최대값으로 세팅 → 출력
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
//RE
class Top implements Comparable<Top>{
int s;
int h;
int w;
Top(int s, int h, int w){
this.s= s;
this.h = h;
this.w = w;
}
@Override
public int compareTo(Top o) {
// TODO Auto-generated method stub
return o.s - this.s;//넓이 내리맛누
}
}
public class Main {
//실행 메인
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb= new Scanner(System.in);
int n = kb.nextInt();
ArrayList<Top> arr = new ArrayList<>();
for(int i=0; i<n; i++) {
int a = kb.nextInt();
int b = kb.nextInt();
int c = kb.nextInt();
arr.add(new Top(a, b, c));
}
Collections.sort(arr);//정렬
int answer= 0;
int[] dy = new int[n];
dy[0] = arr.get(0).h;
for(int i=1; i<n; i++) {
int max_h = 0;
for(int j = i-1; j>=0; j--) {
if(arr.get(j).w > arr.get(i).w && dy[j] >max_h ) {
//즉. j로 앞을 순회하면서, 현재i값보다 w무거우면서, dy[j]값이 가장 큰 값 선택
max_h = dy[j];
}
}
//여기서 세팅
dy[i] = max_h + arr.get(i).h;
answer = Math.max(answer, dy[i]);
}
System.out.println(answer);
}
}
⬛ 백준 1912번. 연속합 | DP
문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
입력
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력
첫째 줄에 답을 출력한다.
풀이
- 여기서 주의할 점은 answer 를 0으로 세팅해두면 안된다는 점.
- 데이터들이 음수로 들어올 경우 0을 최대합으로 인식하기 때문이다.
(1) arr[] 배열에 데이터들을 받았다.
(2) 이 문제는 몇 개를 선택하는 ‘연속된’ 수의 합이 최대합이 되어야 하기 때문에 D[i]의 정의는 i를 마지막으로 선택했을 때의 최대합을 저장하기로 한다.
(3) 그리고 D[i] = Math.max(arr[i], D[i-1] + arr[i]) 로 하여 값을 추출한다.
즉, 현재 i번째값부터 시작하는 값 vs 직전까지의 연속합에 현재 i번째값을 누적하는 합 중에서 더 큰 값으로 세팅하여야 ‘연속된 수의 최대합’을 구할 수 있다.
(4) 그 중에서 가장 max인 D[i] 값을 answer로 출력하면 된다.
package to_0801_1;
import java.util.Scanner;
//1912번. 연속합
public class Main {
//실행 메인
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
int[] arr =new int[n];
for(int i=0; i<n; i++) arr[i] = kb.nextInt();
int[] dy = new int[n];//i를 마지막 선택 항으로 하는 최대합
dy[0] = arr[0];//초기화
int answer = dy[0];//얘로 초기화 해두고
for(int i=1; i<n; i++) {
//직전까지의 합에 연달아 합치기 vs 지금부터 시작하기 중에 더 큰 값으로 세팅
dy[i] = Math.max(arr[i], dy[i-1] + arr[i]);
answer = Math.max(answer, dy[i]);
}
System.out.println(answer);
}
}
⬛ 백준 11055번. 가장 큰 증가하는 부분수열
문제
수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.
풀이
- i로 현재 데이터 arr[i]를 찍고, j는 i부터 0까지 역순으로 앞을 돌면서, 현재 i번쨰 데이터보다 값은 작으면서, dy[j] 중에선 가장 큰 합에 현재의 arr[i]값을 더하는 방식으로 구했다.
package to_0801_2;
import java.util.Scanner;
//11055번. 가장 큰 증가하는 부분수열
public class Main {
//실행 메인
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb= new Scanner(System.in);
int n = kb.nextInt();
int[] arr= new int[n];
for(int i=0; i<n; i++) arr[i]= kb.nextInt();
int[] dy = new int[n];
dy[0] = arr[0];//초기화
for(int i=1; i<n; i++) { //i로 현재값 찍고
int max = 0;
for(int j=i; j>=0; j--) {//j로 i앞을 순회할 거임
if(arr[i] > arr[j] && max < dy[j]) {
max = dy[j];//갱신 계속 시켜줘서 최대 값으로 세팅하려고
}
}
//빠져나온 상태에서 dy[i] 세팅해주기
dy[i] = max+arr[i];//기존 max값에 현재 데이터i도 붙여서 dy[i] 담기
}
int max = Integer.MIN_VALUE;
for(int x : dy) {
max = Math.max(max, x);
}
System.out.println(max);
}
}
⬛ 백준 11722번. 가장 긴 감소하는 부분 수열
문제
수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.
풀이
- D[i] 정의: i번째 수를 마지막 항으로 하여 만들 수 있는 가장 긴 감소 부분 수열 길이
- if(arr[i] < arr[j] && max <dy[j]) 인 값 찾기
- 없다면 기본 1
package to_0801_3;
import java.util.Arrays;
import java.util.Scanner;
//11722번. 가장 긴 감소하는 부분 수열
public class Main {
//실행 메인
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb= new Scanner(System.in);
int n = kb.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++) arr[i] = kb.nextInt();
int[] dy = new int[n];
Arrays.fill(dy, 1);//일단 1로 세팅해두고
int answer = dy[0];
for(int i=1; i<n; i++) {
int max = 0;
for(int j= i; j>=0; j--) {
if(arr[i] < arr[j] && max < dy[j]) {
//현재 i보다 더 큰 값을 가지면서, 그들 중에서 dy[] 값은 max인 애 찾기
max = dy[j];
}
}
dy[i] = Math.max(dy[i], max+ 1);//길이 +1 처리
answer = Math.max(answer, dy[i]);//최대 값을 answer로
}
System.out.println(answer);
}
}
⬛ 백준 1965번. 상자넣기
문제
정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.
상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 작성하시오.
입력
파일의 첫 번째 줄은 상자의 개수 n (1 ≤ n ≤ 1000)을 나타낸다. 두 번째 줄에는 각 상자의 크기가 순서대로 주어진다. 상자의 크기는 1,000을 넘지 않는 자연수이다.
출력
첫째 줄에 한 줄에 넣을 수 있는 최대의 상자 개수를 출력한다.
풀이
- 최대 부분 증가 수열의 길이 구하는 문제와 비슷하다.
- 결국 큰 상자 안에 작은 상자가 들어가는 구조이므로, 최대 상자 개수를 출력하려면 가장 길게 선택할 수 있는 증가하는 상자를 선택한 개수가 될 것이다.
package to_0801_5;
import java.util.Scanner;
//1965번. 상자 넣기
public class Main {
//약간 최대증가부분수열 길이 구하는 느낌과 같다.
//dy[i] 의 정의 : i를 마지막으로 선택했을 때의 최대 길이 정도
//반드시 큰 상자 안에 작은 상자를 담을 수 있다는 것 주의
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb= new Scanner(System.in);
int n = kb.nextInt();
int[] arr= new int[n];
for(int i=0; i<n; i++) arr[i] = kb.nextInt();
int[] dy = new int[n];
dy[0]= 1;
int answer= dy[0];
for(int i=1; i<n; i++) {
int max=0;
for(int j=i; j>=0; j--) {
if(arr[i] > arr[j] && max < dy[j]) {
max = dy[j];
}
}
dy[i] = Math.max(dy[i], max+1);//크기 1 추가하니까
answer = Math.max(answer, dy[i]);
}
System.out.println(answer);
}
}
⬛ 백준 1699번. 제곱수의 합 - DP 문제
문제
어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.
주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)
출력
주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.
풀이
- D[i] 의 정의 : i를 만드는 데 필요한 제곱 항의 최소 개수
- N = 11이라고 한다면, 11을 표현할 때 필요한 제곱항의 최대 값은 3 < 루트11 < 4
- 즉, 3의 제곱일 것이다.
- 그래서 제곱항을 구성할 for(int i=1 ~ 3) 까지로 정하고
- 그 내부에 dy를 구성해줄 j의 값은 (i*i) ~ N 까지로 범위를 지정하여
- dy[j] = Math.min(dy[j] , dy[j - (i*i)] + 1 ] 로 값을 채우면 된다.
package to_0802_1;
import java.util.Arrays;
import java.util.Scanner;
//1699번. 제곱수의 합
public class Main {
//실행 메인
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb= new Scanner(System.in);
int N = kb.nextInt();
int[] dy = new int[N+1];
Arrays.fill(dy, Integer.MAX_VALUE); //일단 최대값을 세팅해두고
dy[0]=0;
dy[1]=1;
int target = (int) Math.sqrt(N);//목표값
for(int i=1; i<=target; i++) { //얘로 제곱항 구할 거고 .
for(int j=(i*i); j<=N; j++) { //i제곱 ~ N까지 순회하면서 더 작은 항의 개수 세팅
dy[j] = Math.min(dy[j], dy[j - (i*i)] + 1); //더 작은 값으로 세팅
}
}
System.out.println(dy[N]);
}
}
⬛ 백준 1695번. 팰린드롬 만들기
문제
앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다.
한 수열이 주어졌을 때, 이 수열에 최소 개수의 수를 끼워 넣어 팰린드롬을 만들려고 한다. 최소 몇 개의 수를 끼워 넣으면 되는지를 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 수열의 길이 N(1≤N≤5,000)이 주어진다. 다음 줄에는 N개의 수열을 이루는 수들이 주어진다. 각 수들은 int 범위이다.
출력
첫째 줄에 끼워 넣을 수들의 최소 개수를 출력한다.
풀이
package to_0808_1;
import java.util.Scanner;
/*백준 1695번. 팰린드롬 만들기 */
public class Main {
//실행 메인
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb= new Scanner(System.in);
int n = kb.nextInt();
int[] nums = new int[n+1];
for(int i=1; i<= n; i++) nums[i] = kb.nextInt();
int[][] dy = new int[n+1][n+1];
for(int i=1; i<=n; i++) { //i로는 수열 길이를 컨트롤
for(int j=1; j<=n-i; j++) { //j로 각 값에 접근
if(nums[j]== nums[j+i]) { //양끝단이 같은 값이면
dy[j][j+i] = dy[j+1][j+i-1];
}else {//양 끝단이 다른 값이면
dy[j][j+i] = Math.min(dy[j+1][j+i], dy[j][j+i-1]) + 1;
}
}
}
System.out.println(dy[1][n]);
}
}
'알고리즘 이론 [개념] > [복습] 코테_알고리즘 복습' 카테고리의 다른 글
| 알고리즘 및 코테 복습 - 그래프(Graph) (0) | 2023.07.24 |
|---|---|
| 알고리즘 및 코테 복습 - 그리디 (Greedy) (0) | 2023.07.18 |
| 알고리즘 및 코테 복습 - DFS, BFS, 이진 탐색 (0) | 2023.07.17 |
| 알고리즘 및 코테 복습 - 구간합, 투포인터, 스택과 큐 (0) | 2023.07.17 |