기록공간

최소 값으로 만들기 위해서는 뺄셈 이후에 나오는 모든 더하기 연산에 괄호를 하면된다. 이 말은 즉슨, 최초로 나오는 뺄셈 이후부터 식이 끝날때까지 뺄셈 연산을 해주면 최소 값을 만들 수 있다. #include #include using namespace std; int main() { string input; cin >> input; string temp = ""; bool checkMinus = false; int result = 0; for (int i = 0; i

우선 최대 구성할 수 있는 팀 수를 구한다. 그리고 인턴쉽 프로그램에 참여하는 수를 남은 학생 수와 빼준다. 하지만 그래도 인턴쉽에 참여해야 할 수가 남아 있으면 구성한 팀에 있는 학생에서 채우면 된다. 남은 인턴쉽 참여 인원을 3으로 나누면 인턴쉽을 보내야 할 팀 수가 나오며, 3으로 나누었을때 한 팀이 또 깨지게 되므로 구한 팀 수에서 1을 더한다. 그리고 앞서 구했던 최대 구성 팀수와 빼주면 된다. #include #include using namespace std; int main() { int girl, boy; int intern; cin >> girl >> boy >> intern; int maxTeam = 0; int tGirl = girl; int tBoy = boy; while (tru..

다음 문제를 풀기 위해서는 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..

그리디 알고리즘은 탐욕 알고리즘이라고도 불린다. 그리디 알고리즘은 커다란 문제를 해결하기 위해 여러 단계를 나누어 해결하는 알고리즘의 하나이다. 여러 경우 중 하나를 결정해야 할 때마다 그 순간의 최적이라고 생각되는 것을 선택해 나가는 알고리즘이다. 하지만 그리디 알고리즘을 적용할 수 있는 예는 많지 않다. 코딩이 쉽고, 구현이 쉬운건 사실이지만, 그리디 알고리즘으로 구한게 항상 최적을 보장하는 경우는 거의 없기 때문이다. 만약에 사탕을 당장 받으면 1개만 받지만, 1분을 기다리면 2개를 받을 수 있다고 하자. 이런 경우 그리디 알고리즘을 사용하면 사탕을 1개 받는 것을 선택한다. 그래서 보통 '근사치 추정'을 위해 그리디 알고리즘을 사용한다. 적용 가능한 예 Prim Algorithm, Kruskal ..