[BOJ] 13902 개업 2 - 동적 계획법
글 작성자: Sowhat_93

동적계획법을 이용하면 쉽게 해결이 가능한 문제이다.
웍의 경우는 동시에 2개를 사용이 가능하므로, 웍의 조합으로 새로운 크기의 웍을 만들고
반복문을 이용해 동적계획법을 사용한다.
N 그릇을 요리한다고 할때, 내가 가진 웍의 크기가 각각 3 4 5 6 이라고 하자.
그렇다면 요리횟수의 최소값은
(N - 3) 그릇을 요리하는 회수 + 1
(N - 4) 그릇을 요리하는 회수 + 1
(N - 5) 그릇을 요리하는 회수 + 1
(N - 6) 그릇을 요리하는 회수 + 1
중 하나이다.
코드로 구현하면 다음과 같다.
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <stdio.h> #include <vector> #include <algorithm> using namespace std; std::vector<int> Works; bool WorkHave[20001] = { false, }; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int MinLabor[10001] = { 4, }; int NumOrder; int NumWorks; int WorkSize; std::cin >> NumOrder; std::cin >> NumWorks; for (int i = 0; i < NumWorks; ++i) { std::cin >> WorkSize; Works.push_back(WorkSize); } for (int i = 0; i < NumWorks; ++i) for (int j = i + 1; j < NumWorks; ++j) { int DualWorkSize = Works[i] + Works[j]; if (WorkHave[DualWorkSize] == false) { Works.push_back(DualWorkSize); WorkHave[DualWorkSize] = true; } continue; } sort(Works.begin(), Works.end()); auto U = unique(Works.begin(), Works.end()); Works.erase(U, Works.end()); for(int i = 1 ; i <= NumOrder; ++i) MinLabor[i] = 10001; MinLabor[0] = 0; size_t HMWorks = Works.size(); for (int i = 0; i < HMWorks; ++i) { int SelectedWorkSize = Works[i]; for (int j = SelectedWorkSize; j <= NumOrder; ++j) { int Pre = j - SelectedWorkSize; if (MinLabor[j] > MinLabor[Pre] + 1) MinLabor[j] = MinLabor[Pre] + 1; } } if (10001 == MinLabor[NumOrder]) std::cout << -1; else std::cout << MinLabor[NumOrder]; return 0; }
이 글은
(새창열림)
본 저작자 표시 규칙 하에 배포할 수 있습니다. 자세한 내용은 Creative Commons 라이선스를 확인하세요.
Creative Commons
본 저작자 표시
'알고리즘' 카테고리의 다른 글
[BOJ] 1932 정수 삼각형 - 동적 계획법 (0) | 2022.01.10 |
---|---|
[BOJ] 12869 뮤탈리스크 - 완전탐색 (0) | 2021.12.03 |
[BOJ] 1904 01타일 - 동적 계획법 (0) | 2021.12.03 |
[BOJ] 14889 스타트와 링크 - Back Tracking (0) | 2021.12.02 |
[BOJ] 1003 피보나치 함수 - 동적 계획법 (0) | 2021.12.01 |
댓글
이 글 공유하기
다른 글
-
[BOJ] 1932 정수 삼각형 - 동적 계획법
[BOJ] 1932 정수 삼각형 - 동적 계획법
2022.01.10 -
[BOJ] 12869 뮤탈리스크 - 완전탐색
[BOJ] 12869 뮤탈리스크 - 완전탐색
2021.12.03 -
[BOJ] 1904 01타일 - 동적 계획법
[BOJ] 1904 01타일 - 동적 계획법
2021.12.03 -
[BOJ] 14889 스타트와 링크 - Back Tracking
[BOJ] 14889 스타트와 링크 - Back Tracking
2021.12.02
댓글을 사용할 수 없습니다.