Dolphins의 HelloWorld

문제링크 : https://www.acmicpc.net/problem/1744 쉬운듯 보이나 의외로 까다로웠던 문제이다. 기본적으로는 음수와 양수별로 나누어 음수는 가장 작은수부터 2개씩 , 양수는 가장 큰 수부터 2개씩 짝을지어 곱해서 더해주면 된다. 그러니까 예를들어 -5 -1 4 2 3 -3 이 있다고 하면 음수는 -5 -3 -1 과 같이 오름차순으로 정렬하여 2개씩 짝지어 곱한 후 더해주고 양수는 4 3 2 와 같이 내림차순으로 정렬하여 2새씩 짝지어 곱한 후 더해주는 식이다. 놓치기 쉬운 부분은 1같은 경우 짝지어 곱해주는 것보다 따로 더해주는게 값을 더 크게한다는 사실이다. 고로 1이 나오는 경우 음수배열에 추가시키지 말고 결과값에 바로 1을 더하도록 한다. 마지막으로 2개씩 짝지어 더하는 과..

문제링크 : https://www.acmicpc.net/problem/1541 한번 마이너스가 나오기 전까지는 값들이 모두 양수로 더해지지만 마이너스가 나오고 난 후에는 그 후의 + 는 모두 - 안에서 괄호로 묶이기 때문에 부호가 무엇이든 빼지는 것으로 생각해도 무방하다. #include #include #include using namespace std; int main() { int result = 0; int first = 0; string str; bool minus = false; cin >> str; int size = str.size(); for (int i = 0; i < size; i++) { if (!minus) { if (str[i] == '+') { result += stoi(str..

문제링크 : https://www.acmicpc.net/problem/11399 생각보다 간단한 문제이다. 오름차순으로 주어진 수들을 정렬한 후 누적해서 더해주면 된다. 나같은 경우에는 for(int i=0; i 이렇게 오름차순으로 정렬된 배열을 배열의 크기 N까지 반복문을 돌릴 때 i번째 배열값이 N-i번 곱해지므로 이렇게 곱해진 것을 더해나갔다. #include #include using namespace std; int arr[1000]; int main() { int N; scanf("%d", &N); for (int i = 0; i < N; i++) scanf("%d", &arr[i]); sort(arr, arr + N); int sum = 0; for (int i = 0; i < N; i++)..

문제링크 : https://www.acmicpc.net/problem/1931 이 문제에 대해 고민을 하다 보면 결국 사용할 수 있는 최대의 회의 수를 출력하기 위해서 회의를 마치는 시간이 중요하다는 것을 알게된다. 회의가 마치는 순서를 오름차순으로 정렬한 후 그 회의가 시작한 시간이 그 전 회의가 끝난 시간과 겹치지 않도록 하면 최대한의 회의 숫자를 구할 수 있다. #include #include #include using namespace std; typedef struct { long long start; long long end; }time; bool cmp(time t1, time t2) { if (t1.end < t2.end) return true; else if (t1.end == t2.en..

문제링크 : https://www.acmicpc.net/problem/11047 위의 문제에서 i>=2인 경우에 A(i)는 A(i-1)의 배수라는 조건이 주어졌으므로 Greedy Algorithm으로 주어진 가장 큰 수부터 시작해서 단위가 큰 돈을 최대한 많이 거슬러주는 식으로 반복문을 작성한다면 쉽게 문제를 풀 수 있다. #include #include using namespace std; vector v; int main() { int N; long long K; cin >> N >> K; long long num; while (N--) { scanf("%lld", &num); v.push_back(num); } long long count = 0; for (int i = v.size() - 1; i..

문제 링크 : https://www.acmicpc.net/problem/1967 트리의 지름을 구하기 위해서는 먼저 기준점을 잡아야되는데 기준점을 잡기위해 루트로부터 가장 길이가 긴 점을 선택한다. 기준점을 잡은 후 기준점으로부터 트리를 탐색하면서 거리의 최댓값을 구하면 답을 구할 수 있다. #include #include #include #include #define SIZE 10001 using namespace std; typedef struct __NODE { int next = -1; int cost = -1; }node; //다음 노드와 가중치 저장 vector v[SIZE]; bool check[SIZE]; pair p = make_pair(0,0); void function(int star..

문제 링크 : https://www.acmicpc.net/problem/11725 #include #include #include #define SIZE 100001 using namespace std; vector tree[SIZE]; //주어진 트리 int ans[SIZE]; //ans[i]는 i 노드의 값을 의미 bool check[SIZE]; //방문한 노드를 check void function() { queue q; q.push(1); // node 1 부터 시작하므로 큐에 push check[1] = true; //1번 노드는 방문했으므로 check while (!q.empty()) { int x = q.front(); q.pop(); //큐에서 하나 꺼냄 for (int i = 0; i < ..

트리의 모든 노드를 방문하는 순서 종류 - preorder (전위순회) - 루트 노드의 방문 - 왼쪽 서브트리의 순회 - 오른쪽 서브트리의 순회 ex) 탐색 순서를 살펴보면 그래프의 DFS순서와 같다는 것을 알 수 있다. - inorder (중위순회) - 왼쪽 서브트리의 순회 - 루트 노드의 방문 - 오른쪽 서브트리의 순회 ex) - postorder (후위 순회) - 왼쪽 서브트리의 순회 - 오른쪽 서브트리의 순회 - 노드방문 ex) 코드짜보기 백준 1991번 문제를 통해 트리의 순회에 대한 코드를 짜는 법을 살펴볼 것이다. 이 문제는 순회의 방법에 따라 코드를 짜는 것 자체가 풀이가 되기 때문에 만약 이 문제를 맞췄다면 어느정도 트리의 순회에 대해 이해를 했다고 볼 수 있을것이다. #include u..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWS2h6AKBCoDFAVT&categoryId=AWS2h6AKBCoDFAVT&categoryType=CODE 우뚝 선 산이 될 수 있는 case를 보면 예를들어 h1 h4 > h5 라고 할 때 h3 앞에 올 수 있는 경우의 수는 ( h1 ) , ( h1 h2 ) => 2가지 이고 h3 뒤에 올 수 있는 경우의 수는 ( h4 ) , ( h4 h5 ) = > 2가지 이다. 고로 우뚝 선 산이 될 수 있는 구간이 될 경우의 수는 2 * 2 = 4 가지 이다. 이런식으로 우뚝 선 산 전후로 오는 경우의 수가 몇가지인지 체크하고 곱한 것을 계속 더해나간..

문제링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWS2dSgKA8MDFAVT&categoryId=AWS2dSgKA8MDFAVT&categoryType=CODE ->사이트에서 직접 문제를 찾아 들어가야함. 풀이 문제를 이해하고 나면 쉽게 풀 수 있는 문제이다. 필요한 사람과 박수를 치고있는 사람을 저장하는 변수를 할당하고 반복문을 통해 자릿수가 0이 아닐때마다 처리해주면 된다. #include #include using namespace std; int main() { int T; scanf("%d", &T); for (int i = 1; i > s; int number = 0; //박수치는 사람 int..