본문 바로가기

다이나믹 프로그래밍72

[백준] 1788번 - 피보나치 수의 확장 [Java] https://www.acmicpc.net/problem/1788 1.  아이디어 N이 0일 때 양수일 때, 음수일 때를 나눠서 해결했다.2. 문제풀이 N이 0일 경우 0 두개를 출력하고 종료했고 N이 양수일 경우 일반적인 다이나믹 프로그래밍을 활용한 피보나치 구현으로, N이 음수일 경우 이항을 통해 점화식을 구해서 동일하게 다이나믹 프로그래밍으로 해결했다. N이 음수일 경우 필요에 따라 절댓값으로 양수처리를 해줘야 한다.3. 코드 import java.io.*;public class Main { private static final int MOD = 1_000_000_000; public static void main(String[] args) throws IOException { .. 2025. 1. 23.
[백준] 2193번 - 이친수 [Java] https://www.acmicpc.net/problem/2193 1.  아이디어 N자리 이친수는 N-1자리 이친수 뒤에 0을 하나 더 붙이거나 N-1자리 이친수 중 0으로 끝나는 이친수 뒤에 1을 붙여서 만들 수 있다.2. 문제풀이 N이 최대 90까지라서 int형 오버플로우가 발생하는 점만 주의하면 된다. 추가로 규칙성을 통해 피보나치 수열을 이루는 점을 알 수 있어서 이를 활용한 1차원 dp 배열로도 해결할 수 있었다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Inpu.. 2025. 1. 23.
[백준] 1149번 - RGB거리 [Java] https://www.acmicpc.net/problem/1149 1.  아이디어 다이나믹 프로그래밍을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 윗집과 아랫집과는 다른 색으로 칠해야하는 문제로 사실 윗집만 고려하면 된다. dp 배열에는 현재 집을 칠하는 경우 칠하는 비용의 최솟값을 저장한다고 할 때 현재 집과 색이 다른 두 윗집 중 칠하는 비용의 누적값이 최소인 집을 고르고 현재 집을 고르면 된다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReade.. 2025. 1. 23.
[백준] 13913번 - 숨바꼭질 4 [Java] https://www.acmicpc.net/problem/13913 1.  아이디어 이전 숨바꼭질 문제에서 최단 경로까지 같이 출력하는 문제로 이전에 방문한 노드를 기록하는 경로 추적 배열을 활용해서 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 1697번 - 숨바꼭질 [Java])2. 문제풀이 before 배열은 이전에 방문한 노드를 기록하는 배열로 시작 위치를 -1로 초기화하고 나머지 위치는 Integer.MAX_VALUE로 초기화 했다. 이후 Queue에 노드를 넣을 때 새 노드의 이전 노드가 어디 위치였는지 before 배열에 기록한 후 K부터 역순으로 before 배열을 탐색하면 경로를 얻을 수 있다. 이때 경로는 역순으로 구해지므로 이를 Stack에 넣었다가 빼는 방식으로 구현했다.3.. 2025. 1. 22.
[백준] 1932번 - 정수 삼각형 [Java] https://www.acmicpc.net/problem/1932 1.  아이디어 Bottom-Up 다이나믹 프로그래밍을 활용해서 해결했다. 삼각형의 크기가 최대 500이어서 DFS 알고리즘으로는 해결할 수 없다.2. 문제풀이 정수 삼각형에서 특정 위치에 대한 최대 경로를 저장하는 dp 배열을 사용했다. 각 위치는 위쪽 두 위치에 대해 최대 경로에 현재 숫자를 더하는 방식으로 점화식을 구성할 수 있고 dp 배열을 모두 채운 후 맨 아래층을 순회하며 최댓값을 찾는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2025. 1. 22.
[백준] 2579번 - 계단 오르기 [Java] https://www.acmicpc.net/problem/2579 1.  아이디어 Bottom-Up 다이나믹 프로그래밍을 활용해서 해결했다. 3개의 계단을 연속해서 오를 수 없는 조건은 2칸 이전 계단에서 얻은 최댓값에서 현재 칸에서 얻는 점수와 3칸 이전 계단에서 얻은 최댓값에 1칸 이전에서 얻은 점수와 현재 칸에서 얻은 점수의 합을 비교하면 된다.2. 문제풀이 구현의 편의를 위해 배열로 다룰 때 앞쪽에 패딩을 넉넉하게 주는 방식으로 구현했다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedR.. 2025. 1. 22.
[백준] 11727번 - 2×n 타일링 2 [Java] https://www.acmicpc.net/problem/11727 1.  아이디어 이전 2×n 타일링 문제에서 2 * 2 타일이 추가된 문제로 동일하게 Bottom-Up 다이나믹 프로그래밍으로 간단하게 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 11726번 - 2×n 타일링 [Java])2. 문제풀이 이전 문제 점화식에서 N-2 일 때 2 * 2 타일을 붙이는 옵션만 추가된 문제로 dp[i] = dp[i-1] + 2 * dp[i-2]로 간단하게 점화식을 구할 수 있다.3. 코드 import java.io.*;public class Main { private static final int MOD = 10_007; public static void main(String[] args).. 2025. 1. 21.
[백준] 11726번 - 2×n 타일링 [Java] https://www.acmicpc.net/problem/11726 1.  아이디어 Bottom-Up 다이나믹 프로그래밍으로 간단하게 해결할 수 있다.2. 문제풀이 1차원 dp 배열을 선언해서 특정 길이일 때 직사각형을 채우는 방법의 수를 저장했다. 길이가 N인 직사각형을 채우는 방법의 수는 길이 N-1일 때 직사각형을 채우는 모든 케이스에 1 x 2 타일 하나를 붙이는 경우와 길이 N-2일 때 직사각형을 채우는 모든 케이스에 2 x 1 타일을 위아래 채우는 경우의 합으로 간단하게 점화식을 구할 수 있다.3. 코드 import java.io.*;public class Main { private static final int MOD = 10_007; public static void main(S.. 2025. 1. 21.
[백준] 11057번 - 오르막 수 [Java] https://www.acmicpc.net/problem/11057 1.  아이디어 행에는 자리수, 열에는 각 자리수에 들어가는 숫자를 저장하는 2차원 dp 배열을 활용한 다이나믹 프로그래밍으로 해결할 수 있었다.2. 문제풀이 오르막 수가 0으로 시작할 수 있어서 풀이가 더 단순했다. 오르막 수를 만들 때 자리수를 뒤로 추가한다고 하면 이전 오르막 수의 1의 자리수보다 같거나 큰 수들이 올 수 있다. N = 1 일 때 0부터 9까지 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 개가 각각 들어가게 되고 N = 2 일 때는 10, 9, 8, 7, 6, 5, 4, 3, 2, 1개가 각각 들어가게 된다. 이를 통해 각 열에 대해 역순으로 순회하며 dp[i][j] =  dp[i-1][j] + dp[i][j.. 2025. 1. 21.
[백준] 11048번 - 이동하기 [Java] https://www.acmicpc.net/problem/11048 1.  아이디어 Bottom-Up 다이나믹 프로그래밍으로 간단하게 해결할 수 있다.2. 문제풀이 미로와 같은 크기의 2차원 dp 배열을 선언했다. dp 배열에는 미로와 같은 위치에서 가져올 수 있는 사탕 개수의 최댓값을 저장했다. 점화식은 dp 배열의 현재 위치에서 얻을 수 있는 사탕의 최대 개수는 현재 위치에 오기 이전 위치에서 얻을 수 있는 사탕의 최대 개수에서 현재 위치에서 얻을 수 있는 사탕의 개수를 더하면 된다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException .. 2025. 1. 21.
[백준] 1890번 - 점프 [Java] https://www.acmicpc.net/problem/1890 1.  아이디어 Top-Down 다이나믹 프로그래밍으로 해결했다.2. 문제풀이 시작 위치를 기준으로 재귀 메서드를 구성하고 이를 메모이제이션을 활용해서 구현했다. 재귀는 위치 정보를 받아서 현재 위치가 도착위치면 1을 반환하고 현재 위치가 점프가 불가능한 0이면 0을 반환하게 했다. 이후 cnt 변수를 통해 현재 위치에서 도착 칸에 갈 수 있는 경우의 수를 각 점프에서 구해서 반환하게 구성했고 이를 dp 배열에 저장했다. 재귀 과정에서 dp 배열이 0이 아닌 해당 칸에서 도착 칸에 갈 수 있는 경우가 저장된 경우 재귀 없이 바로 해당 값을 반환하게 메모이제이션을 적용했다. 일반적인 완전 탐색으로는 시간 초과가 발생하게 돼서 메모이제이션이 .. 2025. 1. 21.
[백준] 1699번 - 제곱수의 합 [Java] https://www.acmicpc.net/problem/1699 1.  아이디어 Bottom-Up 다이나믹 프로그래밍으로 해결했다.2. 문제풀이 주어진 숫자를 최소 개수의 제곱수의 합으로 만들어내는 문제로 dp 배열을 선언한 후 제곱수들은 1로 나머지 수는 무한대로 초기화했다. 이후 dp 배열을 순회하며 각 숫자에 대해 해당 숫자보다 작은 제곱수를 뺀 숫자와 비교해서 최솟값을 저장하는 방식으로 점화식을 구성해서 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buff.. 2025. 1. 21.

티스토리툴바