넘어지고 일어나기 넘어지고 일어나기

링크 : https://www.acmicpc.net/problem/1094 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대를 만들려고 한다. 막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 지민이는 아래와 같은 과정을 거쳐서 막대를 자르려고 한다. 지민이가 가지고 있는 막대의 길이를 모두 더한다. 처음에는 64cm 막대 하나만 가지고 있다. 이때, 합이 X보다 크다면, www.acmicpc.net 접근 - 문제를 그대로 구현한다 - 막대길이를 저장하기 위해 vector를 사용한다 - 막대기를 내림차순으로 정렬한다 - 맨 끝의..

링크 : https://www.acmicpc.net/problem/1963

Link : https://www.acmicpc.net/problem/2668 접근 dfs cycle을 이루는 노드들이 몇개인지 확인 한다 1 2 3 4 5 6 7 3 1 1 5 5 4 6 1 - 3 - 1 3 - 1 - 3 5 - 5 pivot 과 숫자를 함께 넘겨 준다 만약 pivot으로 부터 출발하여 노드 값이 pivot과 동일한 숫자가 나온다면 답에 추가 한다 dfs(int pivot, int node){ if(visited[node]) if( pivot == node ) ret.push_back(pivot) else visited[node] = true dfs(pivot, node) } #include #include #include #include #include #define MAX 101 ..

문제 바로가기 Type : BFS 접근 (1) 경로의 수를 담기 위한 배열을 사용 한다. (2) 한 노드 까지 도달 할 수 있는 경로의 수는 직전 노드까지 도달 할 수 있는 경로수들의 합 이다. (3) 만약 방문 하지 않은 노드 라면 미방문 노드의 경로수를 현재 노드 까지의 경로수로 갱신한다. (4) 만약 방문한 노드 라면 현재 노드 까지의 경로수를 더해 준다. 플로우 차트 구현 코드 #include #include #include #define MAX 100001 using namespace std; int arr[MAX]; int paths[MAX]; map dist; int n, k; bool inRange(int x){ return 0 0; } void bfs(int start){ queue q;..

문제 바로가기 Type : BFS 접근 (1) 외부에서 접근 가능 하도록 지도 주의를 빈곳으로 둘러싼다. (2) 한번의 BFS 당 열쇠를 한개 이상 찾거나 혹은 문서를 발견하는 일을 시도 한다. (3) 만약 시도에 성공 했다면 다시 한번 BFS를 시도 한다. (4) 만약 시도에 실패 했다면 BFS 를 종료 하고 다수의 시도에서 찾은 문서의 갯수를 출력 한다. (5) BFS 탐색 (1) 범위를 벗어나거나, 이미 방문 했거나, 벽이라면 탐색을 하지 않는다. (2) 만약 탐색 지점에 문서가 있다면 카운트 하고, 성공한 시도로 정의한다. (3) 만약 대문자 알파벳을 만났으나, 열쇠가 없다면 탐색을 하지 않는다. (4) 만약 소문자 알파벳을 만났다면, 열쇠를 추가 하고 성공한 시도로 정의한다. 플로우 차트 (1)..

문제 바로가기 Type : BFS 접근 (1) 가능한 모든 물통의 경우를 탐색 하기 위해 BFS 탐색을 실시 한다. (2) 하나의 상태에 진입 할때마다 가능한 모든 경우로 물을 옮겨 본다. (3) 한번 물을 옮길 때 마다 두가지 경우가 가능 하다. * 다른 물통의 물을 전부 채울 수 있는 경우 * 붓는 물통의 물이 전부 비게 되는 경우(4) 다른 물통의 물을 전부 채울 수 있는지 여부는 (size[dst] - water[dst]) < water[src] 로 검사 한다. 플로우 차트 구현 코드 #include #include #include #include #include using namespace std; typedef vector buckets; buckets size; vectorwaters; vo..

문제 바로가기 Type : BFS 접근 문자열 BFS 트리 탐색을 통해 주어진 상태로 부터 목표 상태까지 도달 할 수 있는 최소 거리를 구한다. Tree Example 123495786 193425786 913425789 139425789 (1) 위치 및 현재 상태 파악 string cs = q.front(); int cp = cs.find(&#39;0&#39;); int sy = cp / 3; int sx = cp % 3; 2차원 배열을 사용하지 않고 몫과 나머지를 통해 y와 x 값을 도출 할 수 있다 (2) 만족한 범위 내에서 요소의 순서를 바꾼 새로운 문자열(상태)을 생성 한다. int ny = sy + dy[i]; int nx = sx + dx[i]; np = ny*3 + nx; swap(ns[c..

문제 바로가기 Type : BFS 접근 (1) 수빈이가 동생을 찾기 위한 가장 빠른 경로를 찾기 위해 BFS 탐색을 실시한다. (2) 한 지점을 방문할때 마다 부모 정보를 저장 한다. (3) 부모의 배열을 뒤집어 출력 한다. 자로 구조 (1) arr[MAX] : 탐색을 위한 1차원 배열 (2) parent[MAX] : 부모 정보를 저장할 1차원 배열 (3) map : 탐색 거리를 저장할 map 플로우 차트 (1) BFS 탐색 (2) 경로 출력 구현 코드 #include #include #include #include #include #include #define FAIL "BARK" #define MAX 20001 using namespace std; //자료 구조 선언 map numByRemain; b..