전체 글71 카드 구매하기 ( 백준 11052 ) https://www.acmicpc.net/problem/11052 * dp 문제이다.* 인덱스가 카드 갯수이고 값이 가격이다* pack[1]의 뜻은 카드팩 1개를 지불해야하는 금액* dp[1]의 뜻은 카드팩 1개를 지불해야하는 최대 금액 (최댓값)* 카드 N개 구매시 최댓값을 계산* 차례대로 카드 1개 구매시 최댓값을 dp 배열에 저장 후 출력 * 점화식은 Math.max(dp[i], pack[j] + dp[i-j])* j+(i-j)개의 최댓값을 갱신하면 된다. 즉 i개의 최댓값을 인덱스 별로 계산. import java.io.*;import java.util.*;public class BOJ11052 { public static void main(String[] args) throws IOEx.. 2025. 2. 28. 푼 dp 유형 정리 1. 초급 DP * 1 2 3 더하기https://www.acmicpc.net/problem/9095 - 간단하게 첫번째 두번째 세번째 경우의 수만 구하면 규칙이 보이는 문제.- 여기서 dp는 점화식을 세우기 전에 초기값을 먼저 할당하고 점화식을 세우는게 중요하다고 느낌 * 1로 만들기https://www.acmicpc.net/problem/1463 * 계단 오르기https://www.acmicpc.net/problem/2579 * 포도주 시식https://www.acmicpc.net/problem/2156 - 둘다 3번연속 선택 못 한다는 조건이 존재- 3개의 초기값을 설정 후에 점화식을 세워야함- 계단 오르기는 마지막 계단은 꼭 밟아야 하기때문에 점화식을 세울때 현재 밟고 있는 계단은 꼭 값으로 포함.. 2025. 2. 27. 최대 부분 수열 보호되어 있는 글 입니다. 2025. 2. 27. LIS 가장 긴 증가하는 부분 수열 ( 백준 11053 ) https://www.acmicpc.net/problem/11053 * 배열 중 증가하는 배열을 찾아서 제일 긴 길이를 반환하면 됨* 혼자 생각이 떠오르지 않아서 답을 참고해서 해결* dp 배열을 사용하여 증가 수열 일때마다 최대값으로 갱신 * 각 원소는 길이 1이라는 값을 기본으로 갖고 있으므로 dp 배열을 전부 1로 초기화 시켜줌* 2중 for 루프를 돌면서 포인터 i와j가 증가하는 수열을 탐색함* 그림과 같이 첫 for 루프를 돌릴때 예시인데 j가 10을 가르키고 i가 20을 가르키면 증가하는 수열로 간주함* j포인터에서 길이 1 증가하니까 dp[j]+1과 dp[i]의 최댓값을 비교하여 dp[i]에 길이값을 갱신* 배열 길이만큼 반복하면 끝 import java.io.*;import java.uti.. 2025. 2. 27. 포도주 시식 ( 백준 2156 ) https://www.acmicpc.net/problem/2156 * 포도주를 최대한 많이 마셔야 하는 상황* 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 함* 연속으로 놓여 있는 3잔을 모두 마실 수는 없음* 위 조건에 맞추어서 1-n까지의 번호가 붙어 있는 n개의 포도주 잔이 존재하고 최대한 많은 양을 마셔야 함 * 순서대로 마셔야 하니까 정렬, 그리디 보다는 dp라고 생각했다* 문제에 안마셔야 하는 법은 안적혀 있어서 무조건 마셔야 하는 경우만 생각했다.( 좀 이상한데...? )* 그러면 아래와 같은 점화식이 도출된다.* 초기값-dp[0] : 첫번째 포도주 시식-dp[1] : 첫번째 포도주 + 두번째 포도주 시식-dp[2] : 첫번째 포도.. 2025. 2. 26. 1로 만들기 ( 백준 1463 ) https://www.acmicpc.net/problem/1463 * dp 알고리즘을 활용하는 문제* 순차적으로 증가하는 수열이 아니라서 어떻게 풀어야할지 고민함* dp[] 배열을 사용할때 3가지 연산이 존재함* %2, %3을 해서 나누어 떨어질때 하는 연산들은 2의배수 3의배수 일때만 가능함* -1하는 연산은 어떤 값이든 간에 가능하기 때문에 제일 먼저 연산 시작* dp[i]-1 = dp[i-1] 해서 1되는지 보지만 dp[i] 값을 보기위해 이항해서 dp[i] = dp[i-1] + 1 식을 활용한다* dp[i] = dp[i-1] + 1과 2로 나누어 떨어지면 dp[i/2], 3으로 나누어 떨어지면 dp[i/3] 비교해 최소값으로 갱신* 최종 input 배열에 있는 값을 출력 * 아이패드에 끄적여 보.. 2025. 2. 24. 이전 1 2 3 4 5 6 7 ··· 12 다음
