동적 계획법27 [자바] 백준 14728 - 벼락치기 (java) 목차 문제 : boj14728 필요 알고리즘 DP, 냅색 (배낭 문제) DP로 해결 가능한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 dp[x]를 x시간을 사용해 얻을 수 있는 최대 점수라고 해보자. 그렇다면 현재 단원에 대한 K와 S가 주어졌을 때, x시간을 사용해 얻을 수 있는 최대 점수는, '현재까지 파악한 x시간을 사용해 얻을 수 있는 최대 점수', 'x-K 시간까지 얻을 수 있는 최대 점수에 이번 단원.. 2024. 4. 8. [자바] 백준 24956 - 나는 정말 휘파람을 못 불어 (java) 목차 문제 : boj24956 필요 알고리즘 DP (동적 계획법) DP로 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 'WHE'가 가능한 경우의 수를 찾는다고 생각해보자. 이 경우 매우 직관적으로 가능한데, 하나씩 문자를 살펴보면서 'W'라면 이전까지 나온 W의 수+1, 'H'라면 현재까지 'WH'가 가능했던 경우의 수 + 이전까지 나온 'W'의 수, 'E'라면 현재까지 'WHE'가 가능했던 경.. 2024. 2. 24. [자바] 백준 1309 - 동물원 (java) 목차 문제 : boj1309 필요 알고리즘 DP (동적계획법, 다이나믹 프로그래밍) 기본적인 형태의 DP 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 Nx2 칸으로 동물원이 구성된다. N칸의 세로는 우선 생각하지 말고, 2칸인 가로칸의 존재 가능한 상태를 생각해보자. 다음과 같이 4가지 종류로 존재 가능하다. 다만 이 중 (d)는 가로로 붙어 있게 배치할 수 없다고 하였으므로 불가하여 (a)~(c)의 3가지만 이.. 2024. 2. 21. [자바] 백준 16400 - 소수 화폐 (java) 목차 문제 : boj16400 필요 알고리즘 에라토스테네스의 체, DP (동적 계획법), 냅색 (배낭 문제), 정수론 에라토스테네스의 체로 소수를 전처리 후, 냅색 DP를 돌려서 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 순서대로 생각해보자. 1. N이하의 화폐를 모두 알아야 한다. -> 에라토스테네스의 체 등으로 N 이하의 모든 소수를 미리 구해두자. sqrt(N) 까지만 확인해본 이유는 '에라토스테네스의.. 2023. 12. 15. [자바] 백준 30025 - K의 배수 (java) 목차 문제 : boj30025 필요 알고리즘 DP (동적 계획법), 수학 DP를 이용해 풀 수 있는 문제이다. 풀이를 위해 수학적인 지식이 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 M자리의 양의 정수를 구하고, 그 중 K의 배수가 몇 개인지 구하는 문제이다. 물론 실제로 가능한 모든 M자리 양의 정수를 구해보면 O(N^M) = O(10^100) 이라는 천문학적인 경우의수가 되므로 불가능하다. 그럼 어떻게.. 2023. 12. 12. [자바] 백준 20500 - Ezreal 여눈부터 가네 ㅈㅈ(java) 목차 문제 : boj20500 필요 알고리즘 동적 계획법 (DP), 정수론 정수론 특히 나머지 연산의 성질에 대해 알아야 하고, 효율적으로 풀기 위해 DP가 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 아래와 같이 자리수를 늘려나가 만들어지는 N자리 양의 정수 중 15의 배수가 몇 개인지 구하는 문제이다. 당연하게도 1과 5로 이루어진 N자리 수는 2^N 개나 된다. 2^1515개의 정수는 천문학적인 수치이므로 .. 2023. 12. 5. [자바] 백준 28706 - 럭키 세븐 (java) 목차 문제 : boj28706 필요 알고리즘 DP (동적 계획법) DP로 해결 가능한 문제이다. 이하 풀이는 bit DP (비트필드를 이용한 다이나믹 프로그래밍)로 풀었다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 모든 경우의 수를 본다고 해보자. 1부터 시작해서 차례차례 경우의 수를늘려가는거다. 이러면 당연히 2^200000의 경우의 수가 존재하므로 너무나 천문학적인 수치이다. 그럼 어떻게 해야할까? 이 문제에서 결과.. 2023. 11. 24. [자바] 백준 11108 - TV 전쟁 (java) 목차 문제 : boj11108 필요 알고리즘 동적 계획법 (DP), 그리디 최선의 규칙을 모든 경우에 적용할 수 있는 그리디 문제이고, 직전까지의 최대 값을 알기 위해 DP를 사용했다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제에서 시간의 최대값은 10080이다. dp[x]를 '시간 x까지 획득 가능한 선호도의 최대치' 라고 정의해보자. 예를들어 예제 입력 1을 보자. 1 3 3 8 10 1 4 6 6 4 5 d.. 2023. 11. 21. [자바] 백준 11066 - 파일 합치기 (java) 목차 문제 : boj11066 필요 알고리즘 다이나믹 프로그래밍 (DP, 동적 계획법), 누적합 분할정복 느낌으로 생각해보면 풀이법을 찾을 수 있다. 그리고 구현을 위해 DP와 누적합을 사용해야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선, 이 문제의 경우 연속된 파일끼리만 합칠 수 있다는 점을 주의해야 한다. 만약 아무 파일이나 합칠 수 있었다면 그리디로 매번 합쳐진 파일들 중 가장 가중치가 낮은 2개를 합치.. 2023. 8. 10. [자바] 백준 1311 - 할 일 정하기 1 (java) 목차 문제 : boj1311 필요 알고리즘 bit DP (비트 필드를 이용한 다이나믹 프로그래밍) 비트 단위 DP로 푼 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제를 좀 더 간소화시켜서, N이 항상 3이라고 해보자. 이 때 dp[A][B] 를 A번 사람을 B라는 일의 조합으로 진행한 경우 비용의 최솟값이라고 정의하자. 이 경우 B는 3개의 일을 가지고 할 수 있는 모든 경우를 나타낼 수 있으면 된다. 0. .. 2023. 8. 3. 이전 1 2 3 다음
