다이나믹 프로그래밍16 [백준] 2775번 - 부녀회장이 될테야 [Java] https://www.acmicpc.net/problem/2775 1. 아이디어 다이나믹 프로그래밍으로 간단하게 구할 수 있다.2. 문제풀이 아파트를 2차원 배열로 나타냈을 때 a층 b호에 살려면 a-1층의 1호부터 b호까지의 사람들의 수의 합만큼 사람들을 데려와야하는데 a층 b-1호에 살려면 a-1층의 1호부터 b-1호까지의 사람들을 데려와야 한다. 즉 a층 b호의 사람 수는 a층 b-1호 + a-1층 b호 임을 이용해서 점화식을 작성하는 방식으로 구현했다.아파트의 거주민은 한번만 구하고 재사용해도 되는데 그냥 반복문 안에 깔끔하게 넣었다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws.. 2025. 1. 8. [백준] 2565번 - 전깃줄 [Java] https://www.acmicpc.net/problem/2565 1. 아이디어 다이나믹 프로그래밍 중 LIS 알고리즘으로 해결할 수 있다.2. 문제풀이 전깃줄을 A 전봇대를 기준으로 위에서부터 번호를 매겼을 때 전깃줄이 교차하지 않는 상태는 전깃줄의 순서가 커질수록 B 전봇대에서의 위치가 같이 커져야 한다. 이를 활용해 A 전봇대 위치를 기준으로 정렬한 후 B 전봇대에서의 위치에 대한 LIS를 구하면 이 값이 서로 교차되지 않고 연결될 수 있는 최대 전깃줄의 수이다.문제는 없애야할 전깃줄의 최소 개수를 구해야하므로 처음 주어진 전깃줄의 수에서 LIS의 크기를 뻬주면 된다.3. 코드 import java.io.*;import java.util.*;public class Main { public s.. 2025. 1. 5. [백준] 2225번 - 합분해 [Java] https://www.acmicpc.net/problem/2225 1. 아이디어 Bottom-Up 다이나믹 프로그래밍 또는 중복조합을 활용한 Top-Down 다이나믹 프로그래밍으로 해결할 수 있다.2. 문제풀이 0부터 N까지의 수 중 K개를 선택해서 N을 만드는 경우는 중복조합으로 해결할 수 있다.N을 0 + 1 + 1 + ... + 1 + 0 으로 표현한다면 덧셈 기호는 N+1개가 되고 이 덧셈 기호 중 K-1개를 선택해서 칸막이를 치면 K개의 덩어리를 얻을 수 있다. 이 각 덩어리의 합이 선택한 숫자라고 생각하면 중복조합으로 해결하는 아이디어를 얻을 수 있다. 중복조합 공식 중 nHr = n-1Hr + nHr-1을 이용해서 다이나믹 프로그래밍으로 풀이했다.3. 코드 import java.io.*;i.. 2025. 1. 4. [백준] 2747번 - 피보나치 수 [Java] https://www.acmicpc.net/problem/2747 1. 아이디어 다이나믹 프로그래밍으로 간단하게 피보나치 수를 구할 수 있다.2. 문제풀이 피보나치 수는 이전 두 수의 합이 다음 수가 되므로 이를 배열과 점화식을 적용해서 구현했다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[] dp = new in.. 2025. 1. 4. [백준] 1520번 - 내리막 길 [Java] https://www.acmicpc.net/problem/1520 1. 아이디어 Top-Down 다이나믹 프로그래밍을 활용하면 경로의 개수를 구할 수 있다.2. 문제풀이 특정 위치에서 도착 지점까지 갈 수 있는 경로의 개수는 특정 위치 상하좌우에 위치한 내리막길에서 도착지점까지 갈 수 있는 경로의 개수의 합이다. 이를 dfs로 도착 지점이면 1을 반환하고 도착 지점이 아니면 상하좌우에 내리막길에서 경로의 개수를 더해서 반환하도록 짜면 로직은 구현이 된다. 시간 초과 문제를 해결하기 위해 메모이제이션을 해야하는데 지도와 같은 크기의 2차원 dp 배열을 선언하고 dp 배열에는 특정 위치에서 도착 지점에 갈 수 있는 경로의 개수를 저장한다. 이후 dfs에서 dp 배열에 경로가 저장되어 있으면 해당 개수를 반.. 2025. 1. 3. [백준] 10844번 - 쉬운 계단 수 [Java] https://www.acmicpc.net/problem/10844 1. 아이디어 다이나믹 프로그래밍을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 dp 배열을 2차원 배열로 선언했다. 행은 자리수, 열은 해당 자리수에 온 숫자와 매핑시켜서 가능한 경우의 수를 저장했다.계단 수는 현재 자리에 0이 오는 경우, 9가 오는 경우, 나머지 숫자가 오는 경우로 나눌 수 있고 0이 오는 경우는 앞 자리 수가 1인 경우, 9가 오는 경우는 앞자리 수가 8인 경우, 나머지 숫자 N이 오는 경우는 앞 자리 수가 N-1 또는 N+1인 경우다.이를 2중 for문을 통해 갱신하며 저장시켰고 중간에 1,000,000,000으로 나누어서 오버플로우를 방지하려고 했다. 그럼에도 오버플로우가 발생하기 쉬워서 dp 배열도 lo.. 2025. 1. 2. [백준] 2156번 - 포도주 시식 [Java] https://www.acmicpc.net/problem/2156 1. 아이디어 다이나믹 프로그래밍을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 dp 배열에는 현재 잔까지 주어졌을 때 마실 수 있는 최댓값을 저장했다.점화식은 현재 잔을 마시는 경우와 마시지 않는 경우 중 최댓값을 저장하고 현재 잔을 마시는 경우는 다시 3칸 왼쪽 잔을 마시고 1칸 왼쪽 잔을 마시고 현재 잔을 마시는 경우와 2칸 왼쪽 잔을 마시고 현재 잔을 마시는 경우 중 최댓값을 저장한다.편의를 위해 배열에는 각각 앞쪽에 패딩을 해줬다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { .. 2025. 1. 2. [백준] 9465번 - 스티커 [Java] https://www.acmicpc.net/problem/9465 1. 아이디어 다이나믹 프로그래밍을 활용하면 최댓값을 구할 수 있다.2. 문제풀이 스티커를 떼면 상하좌우에 있는 스티커는 떼어낼 수 없다. 이를 활용해서 2차원 배열 map에 스티커의 점수를 저장하고 같은 크기의 dp 배열을 만들었다. dp 배열은 해당 위치의 스티커를 뗐을 때 점수의 최댓값을 저장하는데 해당 위치의 스티커를 뗐을 때 최댓값은 왼쪽 대각선에 있는 스티커까지 뗀 경우와 왼쪽 대각선보다 한칸 왼쪽에 있는 스티커를 뗀 경우 두가지 중 최댓값과 비교하는 방식으로 동작한다. 바로 왼쪽 스티커를 뗀 경우에는 현재 위치의 스티커를 뗄 수 없고 왼쪽으로 2칸 위치의 스티커를 뗀 경우에는 왼쪽 대각선 스티커를 떼도 되기 때문에 2가지 .. 2025. 1. 1. [백준] 15486번 - 퇴사 2 [Java] https://www.acmicpc.net/problem/15486 1. 아이디어 기존 퇴사 문제에서 N의 크기가 커진 문제로 다이나믹 프로그래밍을 통해서 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 14501번 - 퇴사 [Java])2. 문제풀이 기존 퇴사 문제의 다이나믹 프로그래밍 풀이에서 N의 크기와 상담 종료일이 오버됐을 때를 위한 패딩만 변경하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Input.. 2025. 1. 1. [백준] 14501번 - 퇴사 [Java] https://www.acmicpc.net/problem/14501 1. 아이디어 부분집합을 이용한 완전탐색과 다이나믹 프로그래밍 두 가지 방법으로 풀 수 있었다.2. 문제풀이 1. 부분집합N이 최대 15까지여서 상담을 선택하는 경우의 수가 2^15가지가 나왔다. 이정도면 완전 탐색으로도 충분하다고 생각되서 visited라는 boolean 타입 배열에 각 상담을 진행하는 경우 true, 진행하지 않는 경우 false를 저장한 후 findMax 메서드에서 해당 일정이 중복 또는 퇴사일에 맞게 가능한 일정인지 판단하고 가능한 경우면 최대 수익을 갱신하며 정답을 구했다. 2. 다이나믹 프로그래밍dp 배열에는 해당일에 얻을 수 있는 최대 수익을 저장한다. dp 배열은 현재 상담을 진행했을 때 최대 수익과 .. 2025. 1. 1. [백준] 12852번 - 1로 만들기 2 [Java] https://www.acmicpc.net/problem/12852 1. 아이디어 이전 1로 만들기 문제에서 연산 경로 출력이 추가된 문제로 특정 숫자를 만들기 위해 연산 횟수가 최소가 되는 이전 숫자를 저장하는 배열을 활용하면 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 1463번 - 1로 만들기 [Java])2. 문제풀이 Bottom-Up 다이나믹 프로그래밍 과정에서 해당 숫자를 만드는데 필요한 연산의 횟수가 가장 작았던 이전 숫자를 dp배열과 같은 크기의 배열에 별도로 저장한다. 이후 해당 배열을 이용해서 N부터 거슬러가며 경로를 StringBuilder에 저장한 후 출력했다. 이전 1로 만들기 문제에서는 6의 배수일 때, 3의 배수일 때, 2의 배수일 때, 아무것도 아닐 때로 경우의 .. 2024. 12. 29. [백준] 1463번 - 1로 만들기 [Java] https://www.acmicpc.net/problem/1463 1. 아이디어 다이나믹 프로그래밍 또는 BFS를 이용해서 해결할 수 있다.2. 문제풀이 다이나믹 프로그래밍은 Top-Down, Bottom-Up 그리고 BFS 총 3가지 방식으로 풀었다. Bottom-Up 다이나믹 프로그래밍은 2부터 N까지 각 숫자를 만드는데 필요한 연산의 최솟값을 찾는 방식으로 풀었다.특정 숫자가 6의 배수라면 해당 숫자는 3으로 나눈 수에서 3을 곱했거나 2로 나눈 수에서 2를 곱했거나 1 작은 수에서 1을 더해서 만들었을 때 연산의 횟수가 최소가 된다.특정 숫자가 3의 배수라면 해당 숫자는 3으로 나눈 수에서 3을 곱했거나 1 작은 수에서 1을 더해서 만들었을 때 연산의 횟수가 최소가 된다.특정 숫자가 2의 배수라.. 2024. 12. 29. 이전 1 2 다음
