기록방

👉 문제링크 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 🔸 문제 분석 🔸 N개의 서쪽 지점에서 M개의 오른쪽 지점으로 다리를 연결 하는 경우의 수를 구한다. 다리는 서로 겹칠 수 없다. 한 지점은 하나의 다리만 놓일 수 있다. 조합으로 접근할 수 있다. N

👉 문제링크 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 🔸 문제 분석 🔸 정수 N을 1로 만드는 가장 적은 연산 수를 출력한다. 연산은 -1, /3, /2 세 가지가 있다. DP, DFS, BFS 모두 풀이 가능하다. 🔸 DP 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { // Input BufferedReader br = new BufferedReader..

👉 문제링크 🔸 문제 분석 🔸 가치의 총 합이 최대가 되도록 배낭에 물건을 담고, 그 값을 출력한다. 전형적인 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..

👉 문제링크 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..

👉 문제링크 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 🔸 문제 분석 🔸 n개의 수열을 입력받고, 가장 긴 증가하는 부분 수열의 길이를 출력한다. 수열의 인덱스 별 부분 수열 길이의 최대값을 저장하는 dp배열을 만들어 값을 구한다. 각 인덱스의 수가 부분 수열의 마지막 수가 됐을 때를 계산해서 그 중 최대값을 구해야 한다. 각 인덱스의 앞쪽에서 수열 원소값이 더 작은 것들 중 dp배열 값이 가장 큰 값을 구한다. 구한 값에 +1..