어흥

문제 링크: https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 레슨의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 레슨과 j번 레슨을 같은 블루레이에 녹화하려면 i와 j 사이의 모든 레슨도 같은 블루레이에 녹화해야 한다. 강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가 www.acmicpc.net 1. 주의할 점 - 이분탐색의 조건을 잘 따져줘야한다(low 이 부분때문에 많이 틀렸는데 아직도 많이 헷갈리는 부분이다. ..

문제 링크: https://www.acmicpc.net/problem/2140 2140번: 지뢰찾기 지뢰찾기는 N×N에서 이뤄지는 게임이다. 보드의 곳곳에는 몇 개의 지뢰가 숨겨져 있고, 지뢰가 없는 칸에는 그 칸과 인접(상하좌우 및 대각선)해 있는 8개의 칸들에 몇 개의 지뢰가 숨겨져 있는지에 대한 정보가 주어진다. 게이머는 게임을 진행하면서 보드의 칸을 하나씩 열게 된다. 만약 그 칸에 지뢰가 있다면 게임이 끝나고, 없는 경우에는 그 칸에 적혀있는 숫자, 즉 그 칸과 인접해 있는 8개의 칸들 중 몇 개의 칸에 지뢰가 있는지를 알 수 있게 된다. 이 www.acmicpc.net 1. 주의할 점 - Queue를 이용해서 매번 검사할 경우 -> TLE 발생 - (N-2)*(N-2)형태의 중앙에 있는 정사각..

문제 링크: https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 문제 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다. 상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다. 거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 www.acmicpc.net 1. 주의할 점 - 다익스트라지만 구조체의 종류가 2개라서 헷갈릴 수 있다(make_pair를 쓰지 않을 경우) - ..

문제 링크: https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 www.acmicpc.net 1. 주의할 점 - 다익스트라 문제지만, 2중 For문이 아닌 Heap형태의 우선순위 큐를 이용해야만 풀 수 있는 문제다. -..

문제 링크: https://www.acmicpc.net/problem/14238 14238번: 출근 기록 스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다. 이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 출근 기록이 "AAC"라는 것은 처음 이틀은 A가 출근했고, 셋째 날엔 C만 출근했다는 뜻이다. A는 매일 매일 출근할 수 있다. B는 출근한 다음날은 반드시 쉬어야 한다. C는 출근한 다음날과 다다음날을 반드시 쉬어야 한다. 따라서, 모든 출근 기록이 www.acmicpc.net 1. 주의할 점 - DFS로 시도할 경우, 3^50의 경우이며 몇 가지 추가조건을 건다고 해도 결과는 TLE - 메모라이..

문제 링크: https://www.acmicpc.net/problem/17073 17073번: 나무 위의 빗물 첫째 줄에 트리의 노드의 수 N과 1번 노드에 고인 물의 양을 의미하는 정수 W가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ W ≤ 109) 다음 N-1줄에 걸쳐, 트리에 존재하는 간선의 정보가 U V의 형태로 주어진다. (1 ≤ U, V ≤ N​​​​, U ≠ V) 이는 양 끝 정점이 각각 U와 V인 간선이 트리에 존재한다는 의미이다. 입력으로 주어지는 트리는 항상 올바른 연결 트리임이 보장되며, 주어지는 트리의 루트는 항상 1번 정점이다. www.acmicpc.net 1. 주의할 점 - 출력값에 소숫점 이하수가 10개 있으므로 cout.precision(11)을 통해 출력 형태를 맞춰..

문제 링크: https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다. www.acmicpc.net 1. 주의할 점 - Tree와 depth를 잘 설정해야한다. - LCA 알고리즘을 정확히 이해해야한다. 2. 구현 - 첫 번째 시도: LCA에 대한 개념을 모르고 Parent,Depth 배열만을 이용해서 구현 -> TLE - 두 번째 시도: LCA에 대한 개념을 익히고 적용 -> lg|Node의 최대갯수|의 올림 만큼만 Tree를 밑으로 판다고 생각한다. Dep..

문제 링크: https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 국가를 나타내는 정수와 이 국가가 얻은 금, 은, 동메달의 수가 빈칸을 사이에 두고 주어진다. 전체 메달 수의 총합은 1,000,000 이하이다. www.acmicpc.net 1. 주의할 점 - 전체 메달 수의 총합이 100만이다. -> 금 X M+ 은 X M + 동 X M (M은 특정 수)로 하기엔 M을 쉽게 생각하지 못했다 - 찾고자 하는 index에 집중하지 말고 해당 index의 금은..