본문 바로가기
728x90

분류 전체보기188

백준 2839 JAVA DP 설탕 배달 https://www.acmicpc.net/problem/2839 5kg과 3kg에 최소의 포대를 사용해서 넣어야 함.5kg을 최대한 많이 넣어야 좋음. 1. 설탕이 5의 배수인지 살펴보고, 배수이면 몫이 정답. 2. 설탕이 3미만인지 본다. 3kg포대가 최소 용량이기 때문에 -1을 리턴한다. 3. 3kg 포대에 하나 채우고, 나머지 설탕을 다시 1번부터 시작해본다. 18kg일 경우 18 -> 5의 배수 아님 / -3 (포대+1) -> 15 -> 5의 배수임 (포대 + 15/5 ) = 1 + 3 = 4 import java.io.*;public class Main { public static void main(String[] args) throws IOException { Buffe.. 2025. 4. 22.
[JAVA/dp]백준 1463 : 1로 만들기 https://www.acmicpc.net/problem/1463 1. 주어진 수 n이 1이 되기 위한 최소 경로의 수를 담아주는 배열 지정. dp[n] = x 면 n이 1이 되기 위한 최소 경로의 수 x를 뜻함. 그렇기 때문에 dp의 길이는 dp[n+1] 로 지정해야함.(0이 들어가니까) 2. dp[0] 과 dp[1]은 0이 됨. 3. 2부터 n까지 반복(n포함) 4. 처음 dp[i]는 전의 경로의 수에서 +1 한 만큼 (i-1 +1 = i 이기 때문에 ) 설정해줌 (-1 수식 반영)dp[i] = dp[i-1]+1 5.2로 나눠지는지 3으로 나눠지는지에 따라서 나눈 몫의 경로의 수 + 몫까지 간 경로 1 dp[i] = dp[i/2] + 1 6. 4번과 5번의 경로의 수를 비교하여 작은 수를 대입해줌.. 2025. 4. 22.
이분탐색 입국심사 JAVA 프로그래머스 코딩테스트 https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr import java.util.*;class Solution { public long solution(int n , int[] times){ long answer = 0; Arrays.sort(times); //오름차순 정렬 long min = 1; long max = (long)times[times.length-1]*2; //배열의 마지막(가장 긴 시간)*대기인원.. 2025. 3. 21.
프로그래머스 동적계획법 사칙연산 JAVA 어려움 https://school.programmers.co.kr/learn/courses/30/lessons/1843 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  1. 연산자를 제외한 숫자의 개수int n = (arr.length + 1)/2; 예를들어 1 + 3 - 5 + 7 - 8 가 있으면arr.length = 9(9+1)/2 = 51, 3,5,7,8 => 5개   2. 뺄샘 연산이 비대칭이기 때문에 maxDP 와 minDP 를 따로 저장해야 한다.MAX- MIN 과 MIN - MAX는 다름5-3 과 3-5 는 다른것처럼 int[][] maxDP = new int[n][n];int[][] minDP.. 2025. 3. 14.
동적계획법(Dynamic Programming) 도둑질 자바 https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr class Solution { public int solution(int[] money) { int answer = 0; //바로 money로 받아오면 dp_first와 dp_second는 각각 money 배열을 새로운 배열로 복사하는 것이 아니라, // money 배열 자체를 가리키게 됩니다. 즉, dp_first, dp_second, money가 모두 같은 배열을 공유하게 됩니다. .. 2025. 3. 14.
728x90