DP20 BOJ 1520 - 내리막길 https://www.acmicpc.net/problem/1520 접근그래프 탐색에서 내리막길로만 건너가는 문제이다. 이 문제의 핵심은 어떻게 모든 경로의 수를 구하냐가 관건이다.기존 BFS, DFS를 사용 시, 모든 경로를 탐색해야 하므로 500x500인 이번 문제에서 시간초과가 발생한다. 이 문제의 핵심은 Y->X와 Z->X로 갈 때, X의 경로의 수는 Y+Z 임을 이용하면 된다.이를 메모이제이션을 통해 DP[movedX][movedY]가 0인 경우(탐색되지 않은 경우)에는 계속 앞으로 전진하고,DP[movedX][movedY]가 0이 아닌 경우(이미 탐색된 경우)에는 DP[X] += DP[movedX][movedY]를 수행하면 된다. 이대로 수행하게 되면 문제가 발생한다.이미 진행된 경로에 대해서 .. 2024. 8. 16. BOJ 7579 - 앱 https://www.acmicpc.net/problem/7579 접근앱 중 최소비용으로 최대의 메모리를 확보하는 문제이다.휴대폰 메모리 M이 정해져있기 때문에, 냅색 문제로 해결할 수 있다.냅색 문제에서 weight와 value는 각각 앱의 비용과 앱의 메모리를 의미한다. 기존 냅색 문제에서 DP[i][j]의 의미는 i번째 앱 시점에서 j의 코스트로 가지는 최대 메모리 사용량이다.이중for문을 돌면서 DP[i][j]를 구하면된다. 그리고 마지막에 DP[i][j]가 M이상인 것 중 첫번째가 답이 된다.왜냐하면 i번째를 살펴볼때 j가 0부터 total(사용할 수 있는 최대 코스트)까지를 살피는 경우는 i번째 앱이 포함될 수도 있고 아닐 수도 있기 때문이다. 코드#include #include #inclu.. 2024. 7. 12. BOJ 17404 - RGB 거리 2 https://www.acmicpc.net/problem/17404 접근기존 RGB 거리 문제에서 첫 번째 집과 마지막 집의 색을 고려하는 조건이 추가된 문제이다.DP를 이용하여 풀게되면 마지막 집을 칠할 때, 첫번째로 어떤 집을 선택했는지 알 수 없다.따라서, 첫 번째 집을 칠할 색을 저장하고 마지막 집의 색을 고려해야 한다. 첫 번째 집을 고르는 경우를 for문을 통해 선택하고, 기존 처럼 진행하면 된다.그러나 여기서 문제되는 부분이 있다. 첫 번째 집을 Red를 선택한다고 가정해보자.dp[1][1] = arr[1][1];for (int i = 2; i 위 코드에서 dp[i][1] = min(dp[i - 1][2], dp[i - 1][3]) + cost[i][1];을 하는 순간 dp[1][1] 대신.. 2024. 7. 1. [그리디 #21] BOJ 7570 - 줄 세우기 https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 1차 시도 처음에 이걸 그리디로 해결하기 위해서 다음과 같이 생각했다. 1. 앞으로 옮겼을 때, 뒤쪽에 자신보다 큰 수들이 많이 위치하는 것을 골라야한다. 2. 뒤로 옮겼을 때, 앞쪽에 자신보다 큰 수들이 많이 위치하는 것을 골라야 한다. 그러나 이것은 금방 틀리다는 것을 알 수 있다. 가령 1,2번이 맞다고 하더라도 순서대로 이어져있지 않으면 문제가 된다. 따라서, 순서를 집중해서 공략하는게 좋겠다고 .. 2024. 2. 27. {BOJ 2839} 설탕 배달 (DP) https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1.. 2023. 9. 24. [DP #24] (BOJ 2225) 합분해 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입력 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출력 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. 접근법 기존 문제들과 비슷하게 풀 수 있다 이 문제는 수 N과 개수 K 두 개의 변수가 필요하므로 이차원 배열로 해결할 수 있다고.. 2023. 9. 7. 이전 1 2 3 4 다음
