다이나믹프로그래밍
-
백준 12847번: 꿀 아르바이트다이나믹프로그래밍(DP) 2020. 11. 27. 12:05
www.acmicpc.net/problem/12847 12847번: 꿀 아르바이트 월세를 내기 바로 전 날 까지 인 n (0 < n ≤ 100,000) 일과 일을 할 수 있는 날 m (0 ≤ m ≤ n) 일이 주어진다. 그 다음 줄 에는 1일부터 n일 까지 일급 Ti가 순서대로 주어진다. (0 < Ti ≤ 1,000,000) www.acmicpc.net #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAX_SIZE 100 #define INF 0x7fffffff #define ..
-
백준 1932번: 정수 삼각형다이나믹프로그래밍(DP) 2020. 11. 26. 18:30
https://www.acmicpc.net/problem/1932 키워드 - 다이나믹프로그래밍, 구현 #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAX_SIZE 100 #define INF 0x7fffffff #define CENDL "\n" #define ll long long #define c_reverse(s) reverse(s.begin(), s.end()) #define c_sort(s) sort(s.begin(), s.end()) #define print_vect..
-
백준 11055 번: 가장 큰 증가 부분 수열다이나믹프로그래밍(DP) 2018. 8. 2. 10:16
https://www.acmicpc.net/problem/11055 1. 문제수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다. 2. 알고리즘키워드 - 다이나믹 프로그래밍 가장 큰 증가 부분 수열중 가장 큰 값은 113 이다. 3. 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#i..
-
프로그래머스 Level 3 > 2 x n 타일링프로그래머스(Programmers) 2018. 7. 3. 20:30
https://programmers.co.kr/learn/courses/30/lessons/12900 1. 문제전형적인 타일링 갯수 세는 문제 2. 알고리즘키워드 - 다이나믹 프로그래밍프로그래머스 알고리즘 문제 개선으로 인하여 효율성 및 테스트 조건 추가 됨 3. 코드 123456789101112131415161718#include #include using namespace std; int solution(int n) { int answer = 0; int dp[600001] = {0,}; dp[1] = 1; dp[2] = 2; for(int i=3; i
-
백준 1912번: 연속합다이나믹프로그래밍(DP) 2018. 7. 3. 10:07
https://www.acmicpc.net/problem/1912 1. 문제n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 숫자는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 2. 알고리즘키워드 - 다이나믹프로그래밍, 브루트 포스 * 접근초기 문제를 풀때 부르트포스로 해결 했었는데. 7달 뒤 보니 채점 기준이 달라져서 시간 초과 되었다. 입력 받는 수열 에서이전 값과의 합이 더크 다면 현재 dp 에 dp[i - 1] + dp[i] 저장 이전 값과의 합이 작다면 현..
-
백준 10986번: 나머지 합다이나믹프로그래밍(DP) 2018. 7. 1. 19:20
https://www.acmicpc.net/problem/10986 1. 문제수 N개 A1, A2, ..., AN이 주어진다. 이 때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 2. 알고리즘키워드 - DP, 부분합참고 - https://www.slideshare.net/Baekjoon/baekjoon-online-judge-10986 3. 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include #..
-
프로그래머스 Level3 > 거스름 돈프로그래머스(Programmers) 2018. 6. 23. 19:00
https://programmers.co.kr/learn/courses/30/lessons/12907 1. 문제Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다. 1원을 5개 사용해서 거슬러 준다.1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다.1원을 1개 사용하고, 2원을 2개 사용해서 거슬러 준다.5원을 1개 사용해서 거슬러 준다.거슬러 줘야 하는 금액 n과 Finn이 현재 보유하고 있는 돈의 종류 money가 매개변수로 주어질 때, Fi..