Knapsack3 [자바] 백준 24395 - 명진이의 신년계획 (java) 목차 문제 : boj24395 필요 알고리즘 DP, 냅색 흔히 냅색이라 부르는 유형의 DP 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 기본적인 냅색 문제인데, 2차원으로 진행된다는 점만 주의하면 된다. dp[x][y]를 빨강 알약 x개, 파란 알약 y로 처방 가능한 위험도의 최대치라고 하자. 이 경우 처방할 빨강, 파랑 알약의 수가 r과 b라고 한다면, dp[x][y] = max(dp[x][y], dp[x-r].. 2023. 7. 13. 백준 2293 자바 - 동전 1 (BOJ 2293 JAVA) 문제 : boj2293 1. 우선 문제를 좀 더 간단히 변경해서 봐보자. 1,2,5의 가치를 가지는 동전이 있고, 그 가치의 합이 10이 되게 하려 한다. 그리고 문제와 다르게 동전의 구성이 같아도 순서가 다르면 다른 경우로 치고 생각해보자. 그럼 1차원 배열을 활용한 dp로 아래와 같이 풀 수 있다. (냅색 문제처럼 풀면 된다.) 1.1 우선 초기값이다. dp[idx]는 1,2,5의 동전들을 가지고 idx의 가치를 가지는 경우의 수를 나타낸다. dp[0]은 실제론 불가하지만, 초기값으로 넣어준다. 그래야 동전 하나를 가지고 표현할 수 있는 경우에 대해서도 별도로 처리하지 않고 점화식 하나로 계산하기 편하다. (예를들어 2의 가치를 표현하려면 동전2짜리 하나만 쓸 수 있다. 식으로는 dp[2-2]이다. .. 2021. 12. 29. 백준 4781 자바 - 사탕 가게 (BOJ 4781 JAVA) 문제 : https://www.acmicpc.net/problem/4781 유명한 DP 활용 문제 유형인 냅색(knapsack) 문제이다. '각 사탕의 개수는 매우 많기 때문에, 원하는 만큼 사탕을 구매할 수 있다.'라는 부분 때문에 냅색에서 난이도가 좀 낮춰지지만, 가격이 실수라서 난이도가 다시 높아진다 ㅋㅋㅋ 결국 실수만 잘 처리할 수 있으면 DP를 사용해 풀 수 있다. 그래도 양심이 있는지 소수점 두번째 자리까지만 주어지고, 최대 100.00 이라서 그냥 100을 곱해서 처리하면 된다. 소수점을 처리할 방법들중 몇가지는 다음과 같다. 1. 주어진 실수에 100을 곱한다. -> 주의점은 입력받은 실수에 100을 곱한 후 +0.1 정도를 해줘서 소수점 오차를 없앤 후 int형으로 형변환 해야한다. 안전.. 2021. 11. 23. 이전 1 다음
