기록공간

다음 문제를 풀기 위해서는 30의 배수가 되기 위한 규칙을 알아야 한다. 입력받은 숫자들 중 0이 항상 포함되어야 한다. 모든 숫자들의 합이 3의 배수여야 한다. 문자열로 입력을 받고 '0'이 포함되는지와 모든 숫자의 총 합이 3의 배수인지 확인해주기만 하면 된다. 만약 모든 조건을 만족한다면, 숫자들을 내림차순으로 정렬하면 입력받은 수를 이용한 30의 배수인 가장 큰 수가 나온다. #include #include #include using namespace std; bool cmp(char a, char b) { return a > b; } int main() { string str; cin >> str; bool checkZero = false; long long totalNum = 0; for (i..

동전 0 문제와 유형이 비슷한 문제이다. 그리디 알고리즘 문제이다. 입력 받은 가격을 1000엔과 빼서 나머지 거스름 돈 값을 구한다. 그리고 500엔부터 차례대로 거스름돈 보다 가치가 적거나 같은 경우 그 가치에 맞는 동전 개수를 구한 후 최종 값에 더해주고, 거스름돈에서 구한 만큼의 가치를 빼주면 된다. 이 작업을 동전 가치가 1엔이 될때까지 혹은 거스름돈이 0엔이 될때까지 반복해주면 된다. 코드는 다음과 같다. #include using namespace std; int main() { int maxMoney = 1000; int coinArr[6] = { 500, 100, 50, 10, 5, 1 }; int change = 0; int changeCoinCount = 0; int price = 0..

우선, 로프들을 오름차순으로 정렬한 후, 그리디 알고리즘을 이용하여 풀면된다. O(n^2)를 사용하면 시간초과가 나므로 이점을 유의해서 풀어야한다. 정렬 후에 할일은 다음과 같다. 배열 가장 처음에 위치하는 가장 길이가 짧은 로프는 모든 로프의 길이보다 작거나 같으므로 개수는 배열의 크기와 같다. 분기를 타며 길이가 길어질수록 로프의 개수를 하나씩 줄여나가면서 들 수 있는 중량을 구해주면된다. 이전에 저장된 들 수 있는 중량보다 현재 계산한 중량이 더 크다면 그 값으로 덮어쓴다. 코드는 다음과 같다. #include #include using namespace std; bool cmp(int a, int b) { return a > inpu..

회의 시간에 대한 문제는 그리디 알고리즘의 대표적인 문제라고 한다. 회의 시간이 끝나는 시간을 기준으로 정렬 한 후, 현재 기준에서 가능한 회의 가장 회의가 빨리 끝나는 것을 고르면 된다. 끝나는 시간이 같은 경우가 있을 수 있는데 (6, 8) (8, 8) 이러한 경우이다. 이런 경우를 고려하여 정렬을 해줘야 한다. 만약 끝나는 시간이 같다면 시작시간을 기준으로 정렬해주면 된다. 회의 시간 정렬이 끝나면, 맨 처음 시작 시간을 기준으로 차례대로 카운트 해나가면 원하는 값을 구할 수 있다. 코드는 다음과 같다. 벡터를 이용하여 회의 시간을 담아 정렬을 하였다. #include #include #include using namespace std; struct Time { int begin; int end; ..

동전의 가치가 가장 높은 것 부터 순차적으로 내려가면서 K보다 가치가 작았을때 그 가치만큼의 동전의 개수를 구해 (나눠주고) 최종값에 더해주고 나머지 값이 있으면 아직 동전을 충분히 채우지 못했으므로 반복해주면 된다. 4200원 동전의 가치 1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000 [1] 50000 -> 10000 -> ... -> 1000(알맞는값) 4200 / 1000 = 4개 4200 - (1000 * 4) = 200원 [2] 1000 -> 500 -> 100(알맞는값) 200 / 100 = 2개 200 - (200 * 2) = 0원(분기 종료) [최종] 4개 + 2개 = 6개 #include using namespace std; int main() {..

정렬을 할 줄 안다면 정말 쉬운 문제이다. 시간의 합이 최소가 되기 위해서는 각 사람이 돈을 인출하는데 필요한 시간을 오름차순으로 정렬하면 된다. 정렬 전 [3 1 4 3 2] 3 3 + 1 = 4 3 + 1 + 4 = 8 3 + 1 + 4 + 3 = 11 3 + 1 + 4 + 3 + 2 = 13 3 + 4 + 8 + 11 + 13 = 39 정렬 후 [1 2 3 3 4] 1 1 + 2 = 3 1 + 2 + 3 = 6 1 + 2 + 3 + 3 = 9 1 + 2 + 3 + 3 + 4 + 13 1 + 3 + 6 + 9 + 13 = 32 #include #include using namespace std; int main() { int personCount = 0; int* personTime = nullptr..

#include using namespace std; class CStar { public: CStar(){ } ~CStar() { if (m_ppArr) { for (int i = 0; i < m_nCount; ++i) { if (m_ppArr[i]) { delete[] m_ppArr[i]; m_ppArr[i] = nullptr; } } delete[] m_ppArr; m_ppArr = nullptr; } } public: int GetCount() { return m_nCount; } public: void Solve(int x, int y, int num) { if (num == 1) { m_ppArr[x][y] = '*'; return; } int divide = num / 3; for (int ..

#include #include using namespace std; class CHanoi { public: int GetCount() { return m_nCount; } public: void InputCount() { cin >> m_nCount; } void Solve(int circleCount, int from, int by, int to) { if (circleCount == 1) { Move(from, to); } else { // 1번째에서 3번째를 거쳐 2번째로 n-1만큼 옮긴다. // 나머지 하나를 1번쨰에서 3번째로 옮긴다. // 2번째에 있는 n-1개를 1번째를 거쳐 3번째로 옮긴다. Solve(circleCount - 1, from, to, by); Move(from, to);..