다이나믹 프로그래밍20 [백준] 2579번 '계단 오르기' - Java https://www.acmicpc.net/problem/2579문제풀이Bottom-UP: 작은 문제에서 큰 문제로다이나믹 프로그래밍을 이용하여 풀이합니다. dp배열은 해당 인덱스의 계단까지 올라갔을 경우의 점수의 합산을 값으로 넣습니다. 올라가는 경우는 O, 올라가지 않는 경우는 X라고 해봅시다.i번째 계단에 올라간다고 할 경우, i-2, i-1, i 번째 계단은 X O O 혹은 O X O 가 될 수 있습니다. 만약 XOO의 경우에는 dp[i] = dp[i-3] + stair[i-1] + stair[i] 가 되고,OXO의 경우에는 dp[i] = dp[i-2]+stai[i-3] 이 됩니다. 그래서 둘 중 큰 값을 dp[i]에 갱신시켜주면서 위로 올라가는 방식의 풀이입니다. import java.io... 2024. 8. 16. [백준] 1495번 '기타리스트' - Java https://www.acmicpc.net/problem/1495문제풀이이 문제의 핵심 조건은1. 연주 순서대로 입력되는 곡2. 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 있음이었습니다. DP를 이용하여 풀이했습니다.v배열에는 시작하기 전에 곡에 줄 수 있는 볼륨의 차이를 담고, dp배열의 인덱스의 의미는볼륨, 즉 m까지 담을 수 있으며 각 밸류의 의미는 곡의 순서를 의미합니다. 즉, v배열의 인덱스를 의미합니다. for(int v_idx=1; v_idx q = new LinkedList(); for(int dp_idx=0; dp_idx= 0) q.add(negative); } } while(!q.isEmpty()) { int idx = q.poll();.. 2024. 8. 13. [백준] 1135번 '뉴스 전하기' - Java https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 문제 코드 import java.io.*; import java.util.*; public class Main { private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); private static final BufferedWriter bw = new BufferedWriter(new Out.. 2023. 8. 31. [백준] 1103번 '게임' - Java https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 문제 코드 import java.io.*; import java.util.*; public class Main { private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); private static final BufferedWriter bw = new BufferedWriter(new .. 2023. 8. 27. [백준] 1162번 '도로포장' - Java https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 문제 코드 import java.io.*; import java.util.*; public class Main { private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); private static final BufferedWriter bw = new.. 2023. 8. 25. [백준] 1234번 '크리스마스 트리' - Java https://www.acmicpc.net/problem/1234 1234번: 크리스마스 트리 첫째 줄에 트리의 크기 N, 빨강의 개수, 초록의 개수, 파랑의 개수가 주어진다. N은 10보다 작거나 같다. 빨강, 초록, 파랑의 개수는 0보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 문제 코드 import java.io.*; import java.util.*; public class Main { private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); private static final BufferedWriter bw = new BufferedWriter(new Ou.. 2023. 8. 23. 이전 1 2 3 4 다음
