C++/자료구조와 알고리듬
7. Implementation
GameStudy
2023. 2. 7. 11:16
7.1 Implementation
해커랭크3DSurface)
공간지각력 싸움.
<hide/>
#pragma once
#include <vector>
using namespace std;
int surfaceArea(vector<vector<int>> A) {
int H = A.size();
int W = A[0].size();
int ResultArea = 0;
for (int i = 0; i < H; ++i)
{
for (int j = 0; j < W; ++j)
{
// 기본적으로 위쪽과 아래쪽의 표면적 (2를 더함)
ResultArea += 2;
// 현재 셀의 높이
int CurrentDepth = A[i][j];
// 왼쪽 셀과의 차이
if (j == 0)
{
ResultArea += CurrentDepth; // 왼쪽 면 노출
}
else {
ResultArea += max(0, CurrentDepth - A[i][j - 1]);
}
// 오른쪽 셀과의 차이
if (j == W - 1)
{
ResultArea += CurrentDepth; // 오른쪽 면 노출
}
else
{
ResultArea += max(0, CurrentDepth - A[i][j + 1]);
}
// 위쪽 셀과의 차이
if (i == 0)
{
ResultArea += CurrentDepth; // 위쪽 면 노출
}
else
{
ResultArea += max(0, CurrentDepth - A[i - 1][j]);
}
// 아래쪽 셀과의 차이
if (i == H - 1)
{
ResultArea += CurrentDepth; // 아래쪽 면 노출
}
else
{
ResultArea += max(0, CurrentDepth - A[i + 1][j]);
}
}
}
return ResultArea;
}
해커랭크ClimbingTheLeaderboard)
순위를 구하는 문제. 단, 중복제거 로직이 필요한 문제.
sort() -> unique() -> erase() 순서의 로직을 통해 중복 제거. 그리고 순서 비교.
<hide/>
#pragma once
#include <vector>
#include <algorithm>
std::vector<int> climbingLeaderboard(std::vector<int> ranked, std::vector<int> player)
{
std::sort(ranked.begin(), ranked.end(), [](int op1, int op2) -> bool { return op1 > op2; }); // 중복 제거 전 정렬 필수.
ranked.erase(std::unique(ranked.begin(), ranked.end()), ranked.end());
// unique() 함수는 자료구조 내의 중복 원소를 맨 뒤로 보내고, 중복 원소들의 시작 위치 iterator를 반환함.
// erase() 함수는 전달 받은 iterator를 기준으로 원소 삭제.
std::vector<int> ResultRank;
int Count = ranked.size();
int Rank = Count - 1;
for (int CurrentPlayerScore : player)
{
while (0 <= Rank && ranked[Rank] <= CurrentPlayerScore)
{
--Rank;
}
ResultRank.push_back(Rank + 2);
// ranked 벡터는 0부터 시작 하므로 +1, 만약 ranked 벡터가 비어있어서 자동으로 1위가 되는 경우에 n은 -1 이므로 보정을 위해 +1.
}
return ResultRank;
}
해커랭크FormingMagicSquare)
미리 배열을 만들어두는 것도 문제푸는데에 중요할 수 있다.
너무 머리를 굴려서 알고리듬화 하려기보다는 가끔은 그냥 배열로 만들어둬서 푸는게 중요할 수 있음.
#pragma once
#include <vector>
#include <algorithm> // sort()
#include <limits> // UINT64_MAX
bool CheckMagicSquare(std::vector<int> InDigits)
{
static const int MagicConstant = 15;
return (InDigits[0] + InDigits[1] + InDigits[2] == MagicConstant &&
InDigits[3] + InDigits[4] + InDigits[5] == MagicConstant &&
InDigits[6] + InDigits[7] + InDigits[8] == MagicConstant &&
InDigits[0] + InDigits[3] + InDigits[6] == MagicConstant &&
InDigits[1] + InDigits[4] + InDigits[7] == MagicConstant &&
InDigits[2] + InDigits[5] + InDigits[8] == MagicConstant &&
InDigits[0] + InDigits[4] + InDigits[8] == MagicConstant &&
InDigits[2] + InDigits[4] + InDigits[6] == MagicConstant);
}
int CalculateCost(std::vector<std::vector<int>>& InSquare, std::vector<int>& InMagicSquare)
{
int Cost = 0;
for (size_t i = 0u; i < 3; ++i)
{
for (size_t j = 0u; j < 3; ++j)
{
Cost += std::abs(InSquare[i][j] - InMagicSquare[i * 3 + j]);
}
}
return Cost;
}
int formingMagicSquare(std::vector<std::vector<int>> s) {
std::vector<int> Digits = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
std::sort(Digits.begin(), Digits.end()); // 순열 전에 정렬하여 모든 경우의 수를 만들어 낼 수 있게끔 함.
size_t MinCost = UINT64_MAX;
do {
if (CheckMagicSquare(Digits) == true)
{
int CalculatedCost = CalculateCost(s, Digits);
MinCost = MinCost < CalculatedCost ? MinCost : CalculatedCost;
}
} while (std::next_permutation(Digits.begin(), Digits.end())); // 순열을 계속 생성
return MinCost;
}
해커랭크TheTimeInWords)
위 문제와 마찬가지로, 알고리듬을 찾는게 아니라 미리 정의된 배열을 이용해서 푸는 문제.
<hide/>
#pragma once
#include <string>
#include <vector>
using namespace std;
string timeInWords(int h, int m) {
vector<string> numbers = { "", "one", "two", "three", "four", "five", "six",
"seven", "eight", "nine", "ten", "eleven", "twelve",
"thirteen", "fourteen", "quarter", "sixteen", "seventeen",
"eighteen", "nineteen", "twenty", "twenty one", "twenty two",
"twenty three", "twenty four", "twenty five", "twenty six",
"twenty seven", "twenty eight", "twenty nine", "half" };
if (m == 0)
{
return numbers[h] + " o' clock";
}
else if (m == 15 || m == 30)
{
return numbers[m] + " past " + numbers[h];
}
else if (m < 30)
{
return numbers[m] + (m == 1 ? " minute past " : " minutes past ") + numbers[h];
}
else if (m == 45)
{
return numbers[60 - m] + " to " + numbers[h % 12 + 1];
}
else
{
return numbers[60 - m] + ((60 - m) == 1 ? " minute to " : " minutes to ") + numbers[h % 12 + 1];
}
}
해커랭크TheBombermanGame)
규칙을 확인하고 패턴을 파악하는 문제.
<hide/>
#pragma once
#include <vector>
#include <string>
using namespace std;
// 폭발 후의 그리드 상태를 반환하는 함수
vector<string> detonate(const vector<string>& InGrid)
{
int RowCount = InGrid.size();
int ColumnCount = InGrid[0].size();
vector<string> ResultGrid(RowCount, string(ColumnCount, 'O'));
for (int i = 0; i < RowCount; ++i)
{
for (int j = 0; j < ColumnCount; ++j)
{
if (InGrid[i][j] == 'O')
{
ResultGrid[i][j] = '.';
if (0 <= i - 1)
{
ResultGrid[i - 1][j] = '.';
}
if (i + 1 <= RowCount - 1)
{
ResultGrid[i + 1][j] = '.';
}
if (0 <= j - 1)
{
ResultGrid[i][j - 1] = '.';
}
if (j + 1 <= ColumnCount - 1)
{
ResultGrid[i][j + 1] = '.';
}
}
}
}
return ResultGrid;
}
vector<string> bomberMan(int n, vector<string> grid) {
if (n == 1)
{
return grid;
}
// 2초일 때 모든 셀이 폭탄으로 가득 찬 상태
vector<string> FullBombGrid(grid.size(), string(grid[0].size(), 'O'));
// 3초일 때 초기 폭탄이 폭발한 상태
vector<string> StateAfterFirstDetonation = detonate(grid);
// 5초일 때 첫 폭발 이후의 폭발 상태
vector<string> StateAfterSecondDetonation = detonate(StateAfterFirstDetonation);
// n이 2초 간격으로 반복되므로 n % 4에 따라 결과 결정
if (n % 4 == 1)
{
return StateAfterSecondDetonation;
}
else if (n % 4 == 3)
{
return StateAfterFirstDetonation;
}
else
{
return FullBombGrid;
}
}
해커랭크TheGridSearch)
3중 반복문 전용문제.
<hide/>
#pragma once
#include <string>
#include <vector>
using namespace std;
string gridSearch(vector<string> G, vector<string> P) {
int GR = G.size(), GC = G[0].size();
int PR = P.size(), PC = P[0].size();
// 그리드의 각 위치에서 패턴이 시작하는지 확인
for (int i = 0; i <= GR - PR; i++)
{
for (int j = 0; j <= GC - PC; j++)
{
bool bFound = true;
// 현재 위치에서 패턴이 존재하는지 검사
for (int x = 0; x < PR && bFound; x++)
{
for (int y = 0; y < PC; y++)
{
if (G[i + x][j + y] != P[x][y])
{
bFound = false;
break;
}
}
}
if (bFound == true)
{
return "YES";
}
}
}
return "NO";
}
백준10709)
<hide/>
#pragma once
#include <iostream>
#include <string>
using namespace std;
int n, m, a[104][104];
string s;
int main()
{
cin >> n >> m;
// 입력 받기
for (int i = 0; i < n; i++)
{
cin >> s;
for (int j = 0; j < m; j++)
{
if (s[j] == '.')
a[i][j] = -1;
else
a[i][j] = 0;
}
}
// 처리 로직
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (a[i][j] == 0)
{
int cnt = 1;
while (a[i][j + 1] == -1)
{
a[i][j + 1] = cnt++;
j++;
}
}
}
}
// 결과 출력
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cout << a[i][j] << " ";
}
cout << "\n";
}
return 0;
}
7.2 문자열
백준9996)
substr() 함수가 핵심인 문제. 접두사와 접미사 문자열을 얻고 비교하면 끝.
<hide/>
#pragma once
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void Solve(int N, const string& pattern, const vector<string>& files) {
size_t StarMarkIndex = pattern.find('*');
std::string PrefixString = pattern.substr(0u, StarMarkIndex);
std::string SuffixString = pattern.substr(StarMarkIndex + 1u); // 문자열에서 *를 찾아서 접두사와 접미사로 분리.
for (const auto& FileName : files)
{
if (FileName.length() < PrefixString.length() + SuffixString.length()) // 파일 이름의 길이가 접두사 접미사를 합친 길이보다 짧으면 일단 실패.
{
std::cout << "NE" << std::endl;
}
else
{
if (FileName.substr(0, PrefixString.length()) == PrefixString &&
FileName.substr(FileName.length() - SuffixString.length()) == SuffixString) // 접두사 접미사 확인.
{
std::cout << "DA" << std::endl;
}
else
{
std::cout << "NE" << std::endl;
}
}
}
}
int main() {
int N;
cin >> N;
string pattern;
cin >> pattern;
vector<string> files(N);
for (int i = 0; i < N; ++i) {
cin >> files[i];
}
Solve(N, pattern, files);
return 0;
}
백준10988)
펠린드롬 확인. reverse() 함수로 간단하게 가능.
<hide/>
#pragma once
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
void Solve(const string& str)
{
std::string ReversedString = str;
std::reverse(ReversedString.begin(), ReversedString.end());
if (str == ReversedString)
{
std::cout << 1 << std::endl;
}
else
{
std::cout << 0 << std::endl;
}
}
int main()
{
string str;
cin >> str;
Solve(str);
return 0;
}
백준11655)
문자열을 특정 규칙에 따라 변환하는 문제. 아스키 인코딩과 문자열 append를 활용하면 끝.
<hide/>
#pragma once
#include <iostream>
#include <string>
using namespace std;
void Solve(const string& input)
{
static const size_t MaxCharacterCount = 26u;
static const size_t ROT13 = 13u;
std::string ResultString = "";
for (const char& Character : input)
{
if ('A' <= Character && Character <= 'Z')
{
ResultString += (Character - 'A' + ROT13) % MaxCharacterCount + 'A';
}
else if ('a' <= Character && Character <= 'z')
{
ResultString += (Character - 'a' + ROT13) % MaxCharacterCount + 'a';
}
else
{
ResultString += Character;
}
}
std::cout << ResultString << std::endl;
}
int main() {
string input;
getline(cin, input);
Solve(input);
return 0;
}
해커랭크Encryption)
1차원 문자열을 2차원으로 변환하는 문제. 특정 문자를 지워주는 erase() 함수도 활용 필요.
중요한 부분은 열과 행을 구하는 로직임. sqrt()와 floor(), ceil() 함수를 활용함.
<hide/>
#pragma once
#include <string>
#include <cmath>
std::string encryption(std::string s) {
s.erase(std::remove(s.begin(), s.end(), ' '), s.end());
size_t StringLength = s.length();
size_t RowCount = static_cast<size_t>(std::floor(std::sqrt(StringLength)));
size_t ColumnCount = static_cast<size_t>(std::ceil(std::sqrt(StringLength)));
if (RowCount * ColumnCount < StringLength)
{
RowCount = ColumnCount;
}
std::string Result;
for (size_t j = 0; j < ColumnCount; ++j)
{
for (size_t i = 0; i < RowCount; ++i)
{
size_t D1Index = i * ColumnCount + j;
if (D1Index < StringLength)
{
Result += s[D1Index];
}
}
if (j < ColumnCount - 1)
{
Result += " ";
}
}
return Result;
}
해커랭크HighestValuePalindrome)
주어진 숫자형태 문자열으로 회문을 만들되, 가능한 최대값이 되게끔 만들어야하는 문제.
<hide/>
#pragma once
#include <string>
#include <vector>
std::string highestValuePalindrome(std::string s, int n, int k) {
std::vector<bool> bModified(n, false);
for (size_t i = 0; i < n / 2; ++i)
{
if (s[i] != s[n - i - 1])
{
s[i] = s[n - i - 1] = std::max(s[i], s[n - i - 1]);
bModified[i] = true;
--k;
}
}
if (k < 0)
{
return "-1";
}
for (size_t i = 0; i < n / 2 && 0 < k; ++i)
{
if (s[i] != '9')
{
if (bModified[i] == true && 1 <= k)
{
s[i] = s[n - i - 1] = '9';
--k;
}
else if (bModified[i] == false && 2 <= k)
{
s[i] = s[n - i - 1] = '9';
k -= 2;
}
}
}
if (n % 2 == 1 && 0 < k)
{
s[n / 2] = '9';
}
return s;
}
7.3 개수 세기
백준1213)
각 알파벳의 등장 횟수를 배열에 저장. 홀수개 알파벳이 두 개 이상이면 실패.
절반 문자열 + 홀수알파벳 + 역순 문자열로 펠린드롬 완성.
<hide/>
#pragma once
#include <iostream>
#include <string>
#include <unordered_map>
#include <algorithm>
#include <vector>
using namespace std;
void makePalindrome(const string& name) {
static const size_t MaxAlphabetCount = 26u;
std::vector<size_t> AlphabetCounts(MaxAlphabetCount, 0u);
for (const char& Alphabet : name)
{
++AlphabetCounts[Alphabet - 'A']; // 알파벳 개수 카운트.
}
size_t OddCount = 0u;
char OddCountAlphabet = '\0';
for (size_t i = 0u; i < MaxAlphabetCount; ++i)
{
if (AlphabetCounts[i] % 2u == 1)
{
++OddCount;
OddCountAlphabet = static_cast<char>(i) + 'A'; // 홀수개인 알파벳의 개수와 홀수개 알파벳이 뭔지 기록.
}
}
if (1u < OddCount) // 홀수개인 알파벳이 2개이상이라면 펠린드롬 불가.
{
std::cout << "I'm Sorry Hansoo" << std::endl;
return;
}
std::string PrefixString = "";
std::string SuffixString = "";
for (size_t i = 0u; i < MaxAlphabetCount; ++i)
{
size_t HalfCount = AlphabetCounts[i] / 2u;
PrefixString += std::string(HalfCount, static_cast<char>(i) + 'A');
}
SuffixString = PrefixString;
std::reverse(SuffixString.begin(), SuffixString.end());
if (1 == OddCount)
{
PrefixString += OddCountAlphabet;
}
std::cout << PrefixString + SuffixString << std::endl;
}
int main() {
string name;
cin >> name;
makePalindrome(name);
return 0;
}
백준9375)
의상 종류의 개수를 세고, 곱의 경우의 수를 활용하여 전체 경우의 수를 구함.
<hide/>
#pragma once
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
void Solve(int n) {
std::unordered_map<string, size_t> ClothTypeCounts;
string ClothName, ClothType;
for (size_t i = 0u; i < n; ++i)
{
std::cin >> ClothName >> ClothType;
++ClothTypeCounts[ClothType]; // 각 의상의 종류를 키로 하는 맵을 통해 의상 종류의 개수를 구해둠.
}
size_t CaseCount = 1u;
for (const auto& Type : ClothTypeCounts)
{
CaseCount *= (Type.second + 1u); // 선택하지 않는 경우의 수 포함하여 모든 경우의 수를 구함.
}
std::cout << CaseCount - 1u << std::endl; // 알몸 상태는 제외.
}
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
Solve(n);
}
return 0;
}
해커랭크SherlockAndTheValidString)
map을 이용하여 문자의 개수를 세고, 빈도 수도 세야하는 문제.
등장하는 빈도수가 1회인지 아닌지가 중요.
<hide/>
#pragma once
#include <string>
#include <unordered_map>
std::string isValid(std::string s) {
std::unordered_map<char, size_t> FrequencyMap;
for (char c : s)
{
++FrequencyMap[c];
}
//'a' 'b' 'c' 'd'
// 2 2 1 1
std::unordered_map<size_t, size_t> FrequencyCountMap;
for (auto& entry : FrequencyMap)
{
++FrequencyCountMap[entry.second];
}
// 1 2
// 2 2
if (FrequencyCountMap.size() == 1)
{
return "YES";
}
else if (FrequencyCountMap.size() == 2)
{
auto it = FrequencyCountMap.begin();
int LeftFrequency = it->first;
int LeftCount = it->second;
it++;
int RightFrequency = it->first;
int RightCount = it->second;
if ((LeftFrequency == 1 && LeftCount == 1) || (RightFrequency == 1 && RightCount == 1))
{
// 둘 중 한 종류의 문자가 등장하는 횟수가 1회인 경우.
return "YES";
}
if ((abs(LeftFrequency - RightFrequency) == 1) && (LeftCount == 1 || RightCount == 1))
{
// 두 문자의 등장 횟수 차이가 1인데, 둘 중 하나의 개수가 1개 일때.
return "YES";
}
}
return "NO";
}
7.4 Two-Pointer
백준1940)
투포인터를 이용해서 두 숫자의 합이 조건에 만족하는지 확인하고 푸는 문제
<hide/>
#pragma once
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void Solve(int M, const vector<int>& materials)
{
std::vector<int> SortedMaterials = materials;
std::sort(SortedMaterials.begin(), SortedMaterials.end(), std::less<int>()); // 투포인터를 위한 정렬
size_t Left = 0u;
size_t Right = SortedMaterials.size() - 1u;
size_t WeaponCount = 0u;
while (Left < Right)
{
int Sum = SortedMaterials[Left] + SortedMaterials[Right];
if (Sum < M)
{
++Left;
}
else if (Sum == M)
{
++Left;
--Right;
++WeaponCount;
}
else if (M < Sum)
{
--Right;
}
}
std::cout << WeaponCount << std::endl;
}
int main() {
int N, M;
cin >> N >> M;
vector<int> materials(N);
for (int i = 0; i < N; ++i) {
cin >> materials[i];
}
Solve(M, materials);
return 0;
}
7.5 Sliding-Window
백준2559)
연속적인 K일의 합을 슬라이딩 윈도우로 구하고, max() 함수로 최대값 구하면 끝.
<hide/>
#pragma once
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void Solve(int K, const vector<int>& temperatures)
{
static const size_t MaxTemperatureCount = temperatures.size();
long long CurrentSum = 0;
for (size_t i = 0u; i < K; ++i)
{
CurrentSum += temperatures[i];
}
long long MaxSum = CurrentSum;
for (size_t i = K; i < MaxTemperatureCount; ++i)
{
CurrentSum = CurrentSum - temperatures[i - K] + temperatures[i];
MaxSum = std::max(CurrentSum, MaxSum);
}
std::cout << MaxSum << endl;
}
int main() {
int N, K;
cin >> N >> K;
vector<int> temperatures(N);
for (int i = 0; i < N; ++i) {
cin >> temperatures[i];
}
Solve(K, temperatures);
return 0;
}
해커랭크BearAndSteadyGene)
A, C, G, T의 이상적인 개수가 뭔지 이해하고, map을 이용해서 각 문자의 개수를 구함.
map에 있는 A, C, G, T 개수를 슬라이딩 윈도우를 통해 조정하는 식.
<hide/>
#pragma once
#include <string>
#include <unordered_map>
int steadyGene(std::string gene) {
int GeneStringLength = gene.length();
int IdealCount = GeneStringLength / 4;
std::unordered_map<char, int> GeneCountMap;
for (char c : gene)
{
++GeneCountMap[c];
}
int MinGeneStringLength = GeneStringLength;
int left = 0, right = 0;
// 슬라이딩 윈도우를 사용하여 유전자 문자열 내의 최소 부분 문자열을 찾는다
while (right < GeneStringLength)
{
--GeneCountMap[gene[right]];
++right;
// 모든 문자의 개수가 이상적으로 만족될 때까지 왼쪽 포인터를 이동한다
while (GeneCountMap['A'] <= IdealCount && GeneCountMap['C'] <= IdealCount &&
GeneCountMap['G'] <= IdealCount && GeneCountMap['T'] <= IdealCount)
{
MinGeneStringLength = std::min(MinGeneStringLength, right - left);
++GeneCountMap[gene[left]];
++left;
}
}
return MinGeneStringLength;
}
해커랭크LarryArray)
3개 숫자를 잡고 정렬되어있는지 체크하는 문제.
rotate() 함수를 통해 오른쪽 회전, is_sorted() 함수를 통해 정렬되어 있는지를 체크하는 식.
<hide/>
#pragma once
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// Larry's Array 정렬 가능 여부 판별 함수
string larrysArray(vector<int> A) {
int Length = A.size();
// 가능한 모든 회전 작업을 수행하여 정렬 시도
for (int i = 0; i <= Length - 3; i++)
{
while (A[i + 1] < A[i] || A[i + 2] < A[i + 1]) // i, i+1, i+2의 세 숫자가 정렬되지 않았다면
{
// 오른쪽으로 회전
rotate(A.begin() + i, A.begin() + i + 1, A.begin() + i + 3);
if (is_sorted(A.begin(), A.end()) == true)
{
return "YES";
}
// 더 이상 회전이 불가능할 경우 break
if (A[i] <= A[i + 1] && A[i + 1] <= A[i + 2])
{
break;
}
}
}
// 배열이 완전히 정렬되었는지 확인
if (is_sorted(A.begin(), A.end()) == true)
{
return "YES";
}
else
{
return "NO";
}
}
7.6 Line-Sweeping
백준2979)
라인스위핑으로 각 시간대에 몇 대의 차가 있는지 체크 후 Switch-Case문으로 해결.
<hide/>
#pragma once
#include <iostream>
#include <vector>
void Solve(int A, int B, int C, std::vector<std::pair<int, int>> trucks)
{
static const size_t MaxTimeLimit = 100u;
std::vector<size_t> CarCounts(MaxTimeLimit, 0u);
for (const auto& Interval : trucks)
{
size_t BeginTime = Interval.first;
size_t EndTime = Interval.second;
for (size_t i = BeginTime; i < EndTime; ++i)
{
++CarCounts[i];
}
}
size_t Fee = 0u;
for (size_t i = 0u; i < MaxTimeLimit; ++i)
{
switch (CarCounts[i])
{
case 1:
Fee += A * 1;
break;
case 2:
Fee += B * 2;
break;
case 3:
Fee += C * 3;
break;
default:
break;
}
}
std::cout << Fee << std::endl;
}
int main() {
int A, B, C;
std::cin >> A >> B >> C;
std::vector<std::pair<int, int>> trucks(3);
for (int i = 0; i < 3; ++i) {
std::cin >> trucks[i].first >> trucks[i].second;
}
Solve(A, B, C, trucks);
return 0;
}
7.7 Greedy
코드업3301)
거스름돈을 최소로 주는 문제라 Greedy를 떠올림. 일단 정렬하여 개수를 구하는 것이 중요.
<hide/>
// 16_Greedy
#include <iostream>
using namespace std;
enum { SIZE = 8 };
int main(void)
{
int n, cnt = 0;
cin >> n;
int MoneyUnits[SIZE] = {50000, 10000, 5000, 1000, 500, 100, 50, 10};
for (int i = 0; i < SIZE; ++i)
{
cnt += n / MoneyUnits[i];
n = n % MoneyUnits[i];
}
cout << cnt;
return 0;
}
프로그래머스Level01예산)
<hide/>
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> d, int budget) {
int answer = 0;
sort(d.begin(), d.end());
size_t uSize = d.size();
for (size_t i = 0; i < uSize; ++i)
{
budget -= d[i];
if (budget < 0)
{
break;
}
++answer;
}
return answer;
}