'Dynamic Programming' 태그의 글 목록
본문 바로가기
728x90

Dynamic Programming9

SCPC 6회 예선 [사다리 게임] SCPC 6회 예선 [사다리 게임] 문제 Practice | codeground 위 Link 에서 "125번 SCPC 6회 예선 [사다리 게임]" 에 해당이 된다. 설명 A 상태 : 아직 가로 이음선을 받기 전 상태 B 상태 : 가로 이음선을 하나 받은 상태 C 상태 : 가로 이음선을 2개 받은 상태 D 상태 : 가로 이음선을 3개 받은 상태 E 상태 : 가로 이음선을 4개 받은 상태 이렇게 해당이 된다. 저렇게 이음선을 하나하나 입력받을 때 마다 I --> J 로 가는 방법에서 고장난 가로 이음선의 최소개수를 계속해서 업데이트를 할 것이다. dp[A][B] = A 에서 B 로 갈 때 고장난 가로 이음선의 최소개수 A 상태에는 I --> J ( I != J ) 에 해당이 되는 경로가 존재하지 않는다. 따.. 2021. 7. 3.
백준 No.7579 [앱] BOJ No.7579 [앱] Problem 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #include #define memory first #define cost second using namespace std; typedef pair PII; int cost_max =.. 2021. 2. 22.
Codeforces Round #703 (div.2) Codeforces Round #703 (div.2) A. Shifting Stacks (solved) Problem Problem - A - Codeforces codeforces.com Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include #include #include using namespace std; typedef unsigned long long ull; int tc; vector dp(101, 0); vector ans; int main() { ios_base::sync_with_std.. 2021. 2. 19.
백준 No.11066 [파일 합치기] Baekjoon Online Judge No.11066 [파일 합치기] Problem 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #incl.. 2021. 2. 7.
백준 No.12865 [평범한 배낭] Baekjoon Online Judge No.12865 [평범한 배낭] Problem 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #include #define weight first #define value second using nam.. 2021. 2. 6.
백준 No.10942 [팰린드롬?] Baekjoon Online Judge No.10942 [팰린드롬?] Problem 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #include #include using namespace.. 2021. 2. 5.
lower_bound, upper_bound lower_bound & upper_bound std::lower_bound - cppreference.com std::upper_bound - cppreference.com Definition lower_bound : 찾고자 하는 값 이상의 수가 처음으로 나오는 곳의 index를 구할때 사용 upper_bound : 찾고자 하는 값보다 큰 수가 처음으로 나오는 곳의 index를 구할때 사용 How to use Binary search를 기반으로 탐색되므로, 탐색되는 vector 혹은 list 는 sort 되어있어야 한다. lower_bound, upper_bound는 구하고자 하는 곳의 iterator를 return 한다. 따라서 실제로 사용할 경우 구한 lower_bound 혹은 upper_bound.. 2021. 2. 4.
백준 No.11049 [행렬 곱셈 순서] Baekjoon Online Judge No.11049 [행렬 곱셈 순서] Problem 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 7.. 2021. 2. 4.
백준 No.1912 [연속합] Baekjoon Online Judge No.1912 [연속합] Problem 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include #include using namespace std; int N; vector nums; void input() { cin >> ::N; nums.assign(N, 0); for (int i = .. 2021. 2. 2.
728x90