꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/2617 DFS(Depth First Search) 알고리즘을 이용해 해당 구슬보다 무겁거나 가벼운 구슬이 전체 구슬의 반 초과인지 확인하는 문제였습니다. 알고리즘은 아래와 같습니다.1. 해당 구슬보다 무거운 구슬과 가벼운 구슬을 입력받습니다.2. 1~N 번째 구슬을 모두 탐색하며 해당 구슬보다 무거운 구슬과 가벼운 구슬이 몇개인지 파악합니다.3. 2번에서 구한 두 값 중 하나라도 전체 구슬의 반 초과이면 절대 중간에 있을 수 없습니다. #include #include #include using namespace std; const int MAX = 100; int N, M; vector heavier[MAX], lighter[M..

문제 링크입니다: https://www.acmicpc.net/problem/2851 정말 간단한 구현 문제였습니다.절대값을 통해 점수를 확인하는 것만 주의하면 쉽게 AC 받을 수 있을 것입니다.(재귀 함수보다는 부분합을 이용해서 푸는게 더 간단할 것 같습니다.) #include #include #include using namespace std; int mushroom[10]; vector result; void simulation(int idx, int sum) { result.push_back(sum); //마지막 버섯까지 확인 if (idx == 9) return; simulation(idx + 1, sum + mushroom[idx + 1]); //버섯 먹기를 중단하면 이어나가기 불가능 } int..

문제 링크입니다: https://www.acmicpc.net/problem/6581 문자열 파싱 문제였습니다.해당 문자열이 같은 줄에 있는지 없는지를 판단해야하는 것만 주의한다면 어렵지 않게 풀 수 있는 문제인 것 같습니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); string s; int sum = 0; bool sameline = false; while (cin >> s) { if (s == " ") { cout

문제 링크입니다: https://www.acmicpc.net/problem/12761 백준 1697번 숨바꼭질(http://jaimemin.tistory.com/581)과 유사한 문제였습니다.8가지 종류에 대해 모두 BFS 알고리즘을 수행하는데 인덱스 범위 초과만 유의해주면 되는 문제였습니다. #include #include #include using namespace std; const int MAX = 100000 + 1; int A, B, N, M; bool visited[MAX]; int BFS(int idx) { queue q; //idx, cnt q.push({ idx, 0 }); visited[idx] = true; while (!q.empty()) { int cur = q.front().f..

문제 링크입니다: https://www.acmicpc.net/problem/2331 간단한 DFS(Depth First Search) 알고리즘 문제였습니다. 알고리즘은 아래와 같습니다.1. A=9999이고 P=5일 때 연산 결과가 최대가 되는데 이 때 값이 30만보다 작으므로 visited 배열 크기를 30만으로 잡았습니다.2. A부터 DFS를 시작하는데 해당 숫자가 방문될 때마다 visited 배열의 해당 인덱스를 1 증가시킵니다.3. visited 배열의 해당 인덱스 값이 3이 된다면 반복 수열이 두번째 반복하는 시점이므로 재귀 함수를 탈출합니다.4. 이후 visited 배열을 전부 방문하면서 한번만 등장한 숫자들의 갯수를 파악하고 결과를 출력합니다. #include #include #include ..

문제 링크입니다: https://www.acmicpc.net/problem/2038 이 문제를 풀기 위해서는 우선 골롱수열을 이해해야합니다.n 1 2 3 4 5 6 7 8 9 f(n) 1 2 2 3 3 4 4 4 5 i) n은 1일 때 f(n)=1로 시작합니다.ii) n은 2일 때 f(n)=2이고 f(n)=2이기 때문에 3번째 인덱스까지 2가 저장됩니다.iii) 3번째 인덱스까지 2가 저장되었으므로(2가 2번 출현) 4번째 인덱스에는 3이 저장됩니다.iv) 3번째 인덱스가 2이므로 3도 2번 출현합니다. 따라서, 5번째 인덱스까지 3이 저장됩니다.v) 5번째 인덱스까지 3이 저장되었으므로(3이 2번 출현) 6번째 인덱스에는 4가 저장됩니다.vi) 4번째 인덱스에 3이 저장되어있으므로 8번째 인덱스까지 4..

문제 링크입니다: https://www.acmicpc.net/problem/10451 간단한 DFS(Depth First Search) 알고리즘 문제였습니다.flood fill 유형 문제에서 컴포넌트 개수 세듯이 하면 AC 받을 수 있습니다. #include #include using namespace std; const int MAX = 1000 + 1; int N; int arr[MAX]; bool visited[MAX]; void DFS(int node) { visited[node] = true; if (!visited[arr[node]]) DFS(arr[node]); } int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int T; cin >..

문제 링크입니다: https://www.acmicpc.net/problem/2463 발상의 전환이 필요했던 유니온 파인드(Union Find) 문제였습니다.같은 학교 학우인 degurii(http://degurii.tistory.com/)의 도움으로 풀 수 있었습니다. 알고리즘은 아래와 같습니다.1. M개의 입력을 받은 뒤 비용을 기준으로 내림차순 정렬을 해줍니다.2. 가중치가 큰 간선부터 이어가면서 간선끼리 이어진 노드들은 같은 집합 연결되어있지 않은 노드들은 다른 집합으로 간주하여 답을 구합니다.3. 즉, 서로 다른 집합이였던 노드들이 같은 집합으로 되기 직전에 계산을 하여 Cost(num1, num2)의 값을 구합니다.3번의 부연 설명으로 예시로 나온 그림을 첨부하였습니다. i) 가중치가 제일 큰 ..

문제 링크입니다: https://www.acmicpc.net/problem/5532 간단한 구현 문제였습니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int L, A, B, C, D; cin >> L >> A >> B >> C >> D; int temp1 = L - (A / C); if (A%C) temp1--; int temp2 = L - (B / D); if (B%D) temp2--; cout

문제 링크입니다: https://www.acmicpc.net/problem/12790 간단한 구현 문제였습니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int test_case; cin >> test_case; for (int t = 0; t > hp >> mp >> attack >> defense >> h >> m >> a >> d; hp = max(1, hp + h); mp = max(1, mp + m); attack = max(0, attack + ..