MZ 개발자

이 문제는 얼마전 포스팅했던 BOJ 1654 랜선 자르기 문제와 100%일치하는 문제이다. 핵심은 적절한 나무 길이를 구하기 위해 이진 탐색을 이용해야하는 것이다. https://devconf.tistory.com/65 BOJ 1654 랜선 자르기 이 문제는 K개의 랜선이 주어지고 이를 이용하여 N 개(이상)의 랜선을 만든는데 랜선의 길이를 가장 길게 만들때 그 랜선의 길이를 구하는 문제이다. 시작 아이디어는 주어진 K개의 랜선으로 N개( devconf.tistory.com #include #include #include #include using namespace std; typedef long long ll; int n, m; vector len; ll result; bool cmp(ll a, ll ..

이 문제의 접근 방법은 현재 가진 연료로 갈수 있는 주유소 중 멈췄을때 가장 많은 연료를 획득할 수 있는 주유소에서 멈추면 된다. 주유소의 위치가 순서대로 들어오지 않기 때문에 주유소 위치를 정렬 시켜주어야 한다. 이후 현재 가진 연료로 멈출 수 있는 모든 주유소에서 얻을 수 있는 연료의 양을 우선순위 큐에 넣고 빼면서 전체 획득한 연료 양을 누적시킨다. #include #include #include #include using namespace std; priority_queue pq; vector v; int n; int l, p; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; for(int i = 0; i < n; i..

이 문제는 K개의 랜선이 주어지고 이를 이용하여 N 개(이상)의 랜선을 만든는데 랜선의 길이를 가장 길게 만들때 그 랜선의 길이를 구하는 문제이다. 시작 아이디어는 주어진 K개의 랜선으로 N개(이상)의 랜선을 만들수 있는지 없는지에 초점을 두었다. 여기서 핵심은 적절한 랜선의 길이를 어떻게 잡는가 이다. 여기서 선택지는 두가지로 다음과 같다. 1. 가장 큰 길이를 기준으로 적절한 랜선 길이를 찾아내기 2. 가장 작은 길이를 기준으로 적절한 랜선 길이를 찾아내기 가장 작은 길이로 적절한 랜선 길이를 찾아낼 경우 최대 랜선의 길이를 구할 수 없다. 예를들어 입력이 2 10 100 4 일때 최대 랜선의 길이는 10 이 되지만 가장 작은 길이를 기준으로 하였을 경우 결과는 4가 된다. 가장 큰 길이의 랜선을 기..

이 문제는 N개의 카드중에서 M개의 카드 숫자가 몇개 있는지 찾는 문제이다. 단순한게 브루트포스 방법 O(n^2)으로 문제를 해결하려고 시도한다면 N = 500000, M = 500000 이므로 시간초과가 발생한다. 따라서 특정 숫자가 어디에 있는지 빠르게 탐색하기 위해 이진탐색으로 접근해야 한다. 이진탐색을 하기 위해서는 우선 상근이의 숫자 카드 N이 오름 차순으로 정렬이 되어있어야 한다. 이때 핵심은 중복된 숫자 카드를 어떻게 표현할 것인가 이다. 오름 차순 정렬 후 앞쪽부터 순회하면서 중복된 숫자를 pair 로 변환 시켜준다. 예를들어 N이 -10, -10, 1, 3, 5, 10, 10, 10 일경우 {-10,2}, {1,1}, {3,1}, {5,1}, {10,3} 과 같은 형태로 변환을 시켜준다...

이 문제는 기본적으로 A - B까지 갈수 있는 경로 중 최단 시간을 구하는 다익스트라 응용 문제이다. 기존에 자주 출제되는 다익스트라는 무방향 그래프로 A - B 까지의 최단 경로와 B - A 까지의 최단 경로는 같다. 하지만 이 문제는 방향 그래프로 A - B 까지의 최단 경로와 B - A 까지의 최단 경로가 다르다. 따라서 문제에서 학생들이 오고 가는데 가장 오래 걸리는 학생의 소요시간을 구하기 위해서는 다익스트라를 두번 돌려주어야 한다. #include #include #include #include #include #define INF 987654321 using namespace std; int n, m, x; vector adj[1001]; int dajik(int start, int end)..

이진트리 순회에 대해 다시 한번 복습 할 수 있는 문제이다. 기본적으로 이진트리 순회 방법은 전위(pre), 중위(in), 후위(post)로 3가지 방법이 존재한다. 이 문제는 단순 이진트리 순회가 아닌 중위, 후위 순서가 주어지고 이를 이용하여 트리를 재구성 하는 문제이다. 이진트리 순회 방법은 아래를 참고하자. 더보기 전위순회 루트 - 왼쪽 노드 - 오른쪽 노드 중위순회 왼쪽 노드 - 루트 - 오른쪽 노드 후위순회 왼쪽 노드 - 오른쪽 노드 - 루트 문제에서 입력은 중위 순서와 후휘 순서가 주어진다. 예를들어 입력이 다음과 같다고 가정해보자. 11 8 4 2 9 5 1 10 6 3 11 7 (중위) 8 4 9 5 2 10 6 11 7 3 1 (후위) 전위 순회를 하기위해서 각 레벨에서 루트를 찾는것이..

이 문제는 이전에 풀었던 문제와 입력 방식만 다른 완전히 같은 문제이다. https://devconf.tistory.com/40 BOJ 1967 트리의 지름 문제를 보고 몇시간 정도 풀이를 생각해보다가 도저히 떠오르지 않아 다른 사람 풀이를 참고하여 아이디어를 얻었다. 문제에 간선의 가중치는 100보다 크지 않는 양의 정수라고 하여 특정 노드 devconf.tistory.com 기본적인 방식은 특정 아무 위치에서 DFS를 통해 길이가 최대가 되는 시작점을 구하고, 그 시작점에서 다시한번 DFS를 돌리면 된다. #include #include #include #include using namespace std; int v; vector adj[100001]; bool visited[100001]; int ..

처음 생각한 방법은 노선 길이가 가장 긴 구간부터 구간에 겹치는지 안겹치는지 확인하려고 하였다. 여기서 발생한 문제는 정류소의 갯수가 3 ~ 1,000,000,000개 이기 때문에 모든 정류소를 배열로 정의할 수 없다. 따라서 어떤 노선이 다른 노선에 포함되는지 안되는지 한번에 알수 있는 방법이 필요하다. 만약 모든 노선 a,b에서 ab 라면 조금 복잡하다. 예를들어 [0~3]와 [9~4]는 위의 방법을 적용할 수 없다. 위의 방법을 적용한다면 겹치는 노선임에도 불구하고 겹치지 않는 유효한 노선이 되버린다. 이를 해결하기 위해 노선을 직선상으로 바꿔보자. a>b 일때 ab 인 모든 노선을 ab 일때 직선상으로 변환하면서 노선을 두개를 추가하였기 때문에 결과에는 중복된 값이 저장된다. 따라서 중복된 값을 ..

문제 풀이의 핵심은 한블럭 이동을 w 대각선 이동을 s라 할때 (0,0) 에서 (1,1)로 갈수 있는 방법중 최소시간을 우리는 구할 수 있다. 즉 s 와 2*w 중 걸리는 시간이 작은 것을 고르면 된다. 단순하게 생각하면 만약 대각선으로 움직이는 것이 직선으로 이동하는것보다 작을 경우 즉 s> x >> y >> w >> s; if(2 * w

문제의 힌트를 보면 잘 이해가 되지 않는다. 상식적으로 웅덩이를 덮을때 시작점에 딱 맞춰서 널빤지를 붙이면 최적이다. 힌트를 보면 웅덩이는 1에서 시작하는데 널빤지를 0에서 부터 붙이기 시작하여 사실상 힌트 오류라고 할수 있다. 실제 맞는 예시는 다음과 같다. .111222.333444555 .MMMMM..MMMM.MMMM 풀이 방법은 각 웅덩이 위치를 백터 v에 넣어 정렬한 후 각 웅덩이 마다 깔수 있는 널빤지를 구해주면 된다. 핵심은 널빤지가 다른 웅덩이를 일부 덮는다면 거기서부터 계속 붙여나가고, 그렇지 않고 널빤지의 끝이 일반 땅이라면 그다음 웅덩이부터 다시 붙여나가면 된다. #include #include #include using namespace std; int main() { ios_bas..