728x90 CodingTest40 백준 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. 동적계획법(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. 프로그래머스 동적계획법(Dynamic Programming) 정수 삼각형 자바 https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 거쳐간 숫자의 최댓값을 구해야 하는데,위에서부터 밑으로 내려오면서 비교하면 복잡해진다. 어차피 최댓값 하나만 구하면 되기 때문에 밑에서부터 올라가면서 최댓값을 더해 마지막 꼭대기에 최댓값이 남도록 하자. 그럴려면 기존의 삼각형이 아닌,더한 값을 저장하는 빈 삼각형이 필요하다.빈 삼각형의 마지막 줄은 기존 삼각형과 동일하다. (베이스 동일) class Solution{ public int solution(int[][] triangle){ .. 2025. 3. 5. 이전 1 2 3 4 ··· 8 다음 728x90