DP40 [백준] 1535번 : 안녕 – JAVA [자바] https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 www.acmicpc.net 문제 문제 풀이 백준 1535번 안녕은 DP, 그중에서도 배낭 문제와 되게 유사한 문제이다. 배낭 문제를 아직 잘 모르면 밑에 있는 링크를 참고하면 되겠다. https://propercoding.tistory.com/50 [알고리즘] 배낭 문제 (Knapsack Problem) 목차 배낭 문제란? 배낭 문제란 담을 수 있는 최대 무게가 정해진 배낭이 있고 각각의 무게와 가치가 주어진 물건들이 주.. 2022. 4. 13. [백준] 17212번 : 달나라 토끼를 위한 구매대금 지불 도우미 – JAVA [자바] https://www.acmicpc.net/problem/17212 17212번: 달나라 토끼를 위한 구매대금 지불 도우미 달나라 토끼들이 사용하는 화폐는 동전뿐이다. 동전의 종류는 1원, 2원, 5원, 7원 이렇게 4종류가 있다. 물건을 사고 동전으로 계산을 하는데 동전의 개수가 최소가 되도록 지불하지 않는 것은 www.acmicpc.net 문제 문제 풀이 백준 17212번 달나라 토끼를 위한 구매대금 지불 도우미는 전형적인 1차원 DP 문제이다. 이 문제는 그리고 백준 1463번 1로 만들기와 되게 유사한 문제이다. 이 문제에서는 n원이 주어졌을 때 1원, 2원, 5원, 그리고 7원짜리 동전을 가장 적게 써서 n원을 만들어야 한다. 예를 한 번 보겠다. n = 1 : 1원짜리 동전 1개를 써서 만들 .. 2022. 4. 12. [백준] 17175번 : 피보나치는 지겨웡~ – JAVA [자바] https://www.acmicpc.net/problem/17175 17175번: 피보나치는 지겨웡~ 혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 www.acmicpc.net 문제 문제 풀이 백준 17175번 피보나치는 지겨웡~은 이전에 많이 풀어봤던 피보나치 문제이다. 이 문제 역시 DP를 이용해서 풀 수 있다. 이 문제에서는 피보나치 함수가 다음과 같이 주어졌다. int fibonacci(int n) { // 호출 if (n < 2) { return n; } return fibonacci(n-2) + fibonacci(n-1); } 그리고 이 피보나치 함수에 인자로.. 2022. 4. 8. [알고리즘] 배낭 문제 (Knapsack Problem) 목차 배낭 문제란? 배낭 문제란 담을 수 있는 최대 무게가 정해진 배낭이 있고 각각의 무게와 가치가 주어진 물건들이 주어졌을 때, 배낭에 담은 물건들의 가치가 최대가 되도록 하게 물건을 고르는 방법을 찾는 문제이다. 배낭 문제 예시 4가지의 물건 ABCD가 있고 배낭의 최대 무게는 5라고 가정하겠다. 무게가 1, 가치가 30인 물건을 A; 무게가 2, 가치가 20인 물건을 B; 무게가 3, 가치가 40인 물건을 C; 그리고 무게가 4, 가치가 10인 물건을 D라고 하겠다. 그리고 우리가 가진 가방의 최대 무게는 5이다. 이때 이 가방에 넣을 수 있는 최대 가치가 몇인지를 구하는 것이다. 예를 들어서 B와 C를 넣어서 총가치가 60이 되도록 가방에 넣을 수 있고, 아니면 A와 D를 넣어서 총가치가 40이 .. 2022. 4. 7. 이전 1 2 3 4 5 6 7 ··· 10 다음 반응형
