다이나믹 프로그래밍 문제입니다. 각 자리수가 한자리 부터 모든 경우의 수를 채우고 다음은 두자리 ... 세자리 ... 네자리 ... n자리 까지 채웁니다. A자리는 A-1자리에서 뒷자리수가 현재 수보다 작은 것들의 합 + 1을 해주면됩니다. 이렇게 되면 9의경우 0~8까지 수를 전부 더한 뒤 + 1을 해줘야하고 8도 0~7까지 수를 전부 더한 뒤 +1을 해줘야합니다. 여러 번 반복해야하는 경우가 생기므로 다른 방법을 찾아보았습니다. 뒷자리수가 B일때 B-1은 나머지 DP[B]의 값을 제외하고 모든 값을 가지고 있습니다. 그래서 DP[B] = DP[B-1] + DP[B]라는 점화식을 세울 수 있습니다. (뒷자리수) DP[1] = DP[1] + 1 DP[2] = DP[2] + DP[2 - 1] + 1 DP[..

그리디 알고리즘 과제를 수행해서 가장 많은 점수를 얻는 문제입니다. 점수를 기준으로 오름차순해서 가장 큰 수부터 마감일에 가깝게 넣어줍니다. 들어갈 곳이 없으면 넘어가고 이를 반복해서 들어간 값들을 전부 더해줘서 출력해줍니다. #include #include #include #include using namespace std; int main(int argc, char *argv[]) { int n; int deadline; int score; int end; int result = 0; int arr[1001]; vector v; memset(arr, 0, sizeof(arr)); cin >> n; for (int i = 0; i > deadline >> score; v...

그리디로 문제를 해결했습니다. 3월1일부터 11월 30일까지 최소의 갯수를 선택해서 꽃을 피고있게 하는 문제입니다. 3월 1일 아래로 입력받은 것은 3월 1일로 변경해주고 12월 1일 위로 입력받은 것은 전부 12월 1일로 변경해주었습니다. 월일을 표현하기 쉽게하기위해서 월에 100을 곱해주었습니다. ex) 3월 1일 = 301, 12월 1일 = 1201 1. 시작점은 3월 1일부터 시작해서 최대한 긴것을 골라줍니다. 2. 시작점 부터 고른것의 도착점 사이에 시작하는 것들을 탐색해서 가장 멀리 가는것을 선택해줍니다. 3. 고른것의 시작위치를 시작점으로, 도착위치를 도착점으로 변경해줍니다. 4. 2~3을 반복합니다. 5. 도착점이 원래 도착점보다 작으면 더이상 진행할 수 없는 경우로 0을 출력합니다. 6...

다이나믹 프로그래밍 문제입니다. 7번까지는 1번(A를 누름)만 누르는 것이 최대입니다. 그 후로는 2가지를 비교합니다. 1. 2, 3, 4(전체 붙여 넣기) 2. 2, 3, 4, 4, 4 ... (복사한것 계속 붙여 넣기) 2번의 경우 계속 붙여넣는것은 3번정도만 비교해주면 충분합니다. 그러면 다음과 같은 4개를 구할 수 있고 이를 비교해서 큰값을 넣어주면 됩니다. DP[i-1] + 1 (A만 누르는 경우) DP[i-3] * 2 (3칸전 값 전체 복사 붙여넣기) DP[i-4] * 3 (4칸전 값 전체 복사 붙여넣기 * 2) DP[i-5] * 4 (5칸전 값 전체 복사 붙여넣기 * 3) #include #include typedef long long ll; using namespace std; int ma..

다이나믹 프로그래밍 문제입니다. 주어진 배낭에 최대한 많은 가치를 담는 문제와 동일한 문제입니다. 다른 점으로는 돈으로 실수(double)가 있는데 돈의 범위는 0.01 ~ 100.00 입니다. 이를 * 100해주어서 integer로 처리할 수 있도록 만들어주면 배낭문제와 동일해집니다. 이 때 double의 오차가 있을 수 있으므로 0.5를 더해주었습니다. #include #include #include #include using namespace std; int n, c; int DP[10010]; double m, p; int mm, pp; vector v; bool compare(const pair &a, const pair &b) { if (a.second == b.second) { return ..

다이나믹 프로그래밍 문제입니다. BOTTOM-UP방식으로 1부터 찾는 수까지 차례대로 만들어가면 됩니다. 1, 2, 3으로 더하므로 N은 다음으로 만들 수 있습니다. N - 1 (1로 더한 경우) N - 2 (2로 더한 경우) N - 3 (3로 더한 경우) 이를 점화식으로 표현하면 다음과 같습니다. DP[i] = DP[i - 1] + DP[i - 2] + DP[i - 3] #include #include #include #include using namespace std; typedef long long ll; int DP[1000001]; int main(int argc, char* argv[]) { int ts; ll num; ll maxNum = 0; vector v; memset(DP, 0, si..

트럭 한대로 한번 한번 이동했을 때 최대 배송할 수 있는 박스 수를 출력하는 문제입니다. 발송위치에서 수신위치로 박스를 보내는데 수신위치를 기준으로 오름차순 정렬을 해줍니다. 차례대로 보낼 수 있는량을 갱신하면서 하는데 예로 설명을 드리겠습니다. https://www.acmicpc.net/board/view/6327에 올려주신 예제를 참고 했습니다. 다음처럼 입력 받았을때 6 60 5 1 2 30 2 5 70 5 6 60 3 4 40 1 6 40 정렬을하면 다음과 같습니다. 1 2 30 3 4 40 2 5 70 1 6 40 5 6 60 1 2 30 30 0 0 0 0 0 (+30 적재) 3 4 40 30 0 40 0 0 0 (+40 적재) 2 5 70 30 20 60 20 0 0 (+20 적재) 1 6 ..

N개의 고속도로 위에 K개의 집중국을 세웠을 때 집중국의 수신 가능 영역의 길이의 최소값을 출력하는 문제입니다. 이는 N을 정렬한 뒤 K개의 묶음으로 나눠서 묶음 내에서의 최대값 - 최소값의 총 합을 구하면 됩니다. 위의 예제의 경우 정렬을 하면 다음으로 나타낼 수 있습니다. 1 3 6 6 7 9 여기서 각 거리의 차이를 구해줍니다. 2 3 0 1 2 길이의 최소값을 구해야하므로 가장 긴 거리를 지워줘야 합니다. 집중국의 개수 K - 1개 만큼 가장 긴 길이를 지울 수 있다고 보면 됩니다. K = 2이므로 1개를 지울 수 있다고 생각했을때 가장 큰 3을 지워줍니다. 그리고 나머지 거리들을 전부 더해주면 수신 가능 영역의 길이의 총 합을 구할 수 있습니다. #include #include #include ..