기록방

👉 문제링크 🔸 문제 분석 🔸 가치의 총 합이 최대가 되도록 배낭에 물건을 담고, 그 값을 출력한다. 전형적인 dp문제이다. 가방의 무게 제한을 0부터 k까지 늘려가며 최적값을 누적해 간다. 한 물건에 대해, 넣었을때와 안넣었을때 어느 값이 더 최적인지 비교해 가며 누적해 간다. 무게 제한이 k이면서 모든 물건이 고려된 최종 결과를 출력한다. dp를 2차원 배열로 구현한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public s..

👉 문제링크 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 🔸 문제 분석 🔸 고정된 위치의 숫자와, 그 사이에 하나 씩 들어갈 수 있는 4종류의 연산자들의 개수가 주어진다. 계산으로 만들 수 있는 값의 최대값과 최소값을 출력한다. 연산자 자리를 바꾸면 값이 달라지기 때문에 순열로 풀이할 수 있다. 같은 종류의 연산자는 자리를 바꿔도 중복계산이기 때문에 dfs나 nextpermutation으로 중복을 제거할 수 있다. 🔸 순열 🔸 import java.io..

👉 문제링크 19621번: 회의실 배정 2 서준이는 아빠로부터 N개의 회의와 하나의 회의실을 선물로 받았다. 각 회의는 시작 시간, 끝나는 시간, 회의 인원이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, www.acmicpc.net 🔸 문제 분석 🔸 회의 시간에 진행할 수 있는 회의를 조절해, 회의에 참여한 인원의 최대값을 출력한다. 회의 별 최대 참여 인원을 DP에 저장하는 방식으로 풀이할 수 있다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokeni..

👉 문제링크 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 🔸 문제 분석 🔸 0부터 10만까지 범위에서, 수빈이의 위치 N 부터 동생의 위치 K로 이동하는 최단 시간을 출력한다. 수빈이가 이동하는 방법은 좌우 한칸(-1, +1), 순간이동 (현위치 *2)가 있다. 주의 할 점은 이동위치와 k의 거리 차이가 가장 적은 것을 선택하는 그리디 방식으로 계산해서는 안된다. 그리디로 보면 예제 1번에서 5 - 10 - 9 - 18 - 17 에서 2번째 이동 할 때인 10위치에서 순간이동이 ..

👉 문제링크 1954번: 화학실험 우리에게는 n가지 종류의 화학 시약 t1, t2, ..., tn과 M mg의 용액이 있다. 이 용액 중 x mg을 시약 ti에 넣으면 aix+bi만큼의 어떤 가스가 발생한다고 한다. 시약에 넣을 수 있는 용액의 양은 자연수이 www.acmicpc.net 🔸 문제 분석 🔸 n 종류의 화학 시약 t1, t2, ..., tn의 정보 ai와 bi, 그리고 M mg의 용액이 주어진다. 용액 중 x mg을 시약 ti 에 넣으면 ai*x+bi 만큼의 가스가 발생한다. n개의 화학 시약 모두 같은 양의 가스를 발생시킬 수 있으면 가스 양을 출력하고, 그럴 수 없으면 0을 출력한다. 용액이 남으면 안된다. 용액의 양 x mg 을 1부터 늘려가며 용액들에 넣어보고 같은 양의 가스가 발생하..