김머성 블로그

[BAE/<JOON> 문제풀이] 1647. 도시 분할 계획

www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 주어진 간선으로 MST를 구성하고 그 간선내의 가장 큰 간산 하나를 제거하면 정답을 얻을 수 있다 더보기 #include #include #include using namespace std; struct h { int x, y, v; }; bool cmp(h a, h b) { return a.v < b.v; } int parent[100001]; int findp(int x..

[BAE/<JOON> 문제풀이] 14003. 가장 긴 증가하는 부분 수열 5(풀이 미완)

www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net #include #include #include #include using namespace std; struct trackball { int idx, val; }; int main() { int n; cin >> n; vector arr(n + 1); vector dp; vector track(n + 1); for (int i = 1; i > arr[i]; } dp.push_ba..

[BAE/<JOON> 문제풀이] 9328. 열쇠

www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 시뮬레이션 문제인데 생각보다 까다로웠다. 결국 코너케이스 해결 못해서 테스트 케이스 받아서 까봤다. 풀이:: 열쇠가 알파벳이므로 비스마스크로 2^26이므로 int 범위를 벗어나지 않는다. 따라서 방문체크 배열에 열쇠 상태를 저장하며 새로운 열쇠가 있는 경우에만 탐색을 허용한다. 칸을 방문했다면 해당 칸에 접근했던 모든 열쇠들을 가지고 지역 탐색을 시작한다. 만약 열 수 없는 문에 방문한 경우에도 해당 칸에 열쇠 상태는 저장..

[BAE/<JOON> 문제풀이] 9466. 텀 프로젝트

www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이:: 1차 탐색에서 요소들에 1표시를 하고 스택에 넣으며 중복되는 지점을 찾는다. 중복 지점(1표시)을 찾으면 해당 인덱스가 나올 때 까지 스택을 POP 시키며 요소들에 2표시를 하고 갯수를 셈 만약 1표시를 찾기전에 2표시를 찾으면 해당 탐색 종료(이미 탐색된 루트임) 스택에 남은 요소들도 모두 2표시를 하고 다음 탐색되지 않은 인덱스 탐색 1표시 : 1차 루프 탐색 2표시 : 탐색 완료 표시 더보기 #incl..

[BAE/<JOON> 문제풀이] 1806. 부분합

www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 투포인터 알고리즘:: 탐색범위 내의 2개의 포인터*를 잡고 각각의 위치를 조절해가며 탐색하는 기법 풀이:: 문제에서 요구하는 조건은 구간의 합이 주어진 K 이상일 때의 구간의 최소 길이이므로 미리 구간합을 구해두면 2개의 인덱스 사이의 합을 상수시간에 구하며 탐색 할 수 있다. 두 인덱스 s와 e사이의 합을 구간합으로 구하며 합이 K보다 크다면 s를, 작다면 e를 늘려가며 최소 길이를 구한다. 만..

[BAE/<JOON> 문제풀이] 1311. 할 일 정하기 1

www.acmicpc.net/problem/1311 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net 서론 || 처음에는 기업 투자와 비슷해 보였지만 외판원과 매우 비슷한 문제 풀이 || 일의 상태를 비트마스크로 치환하고 각각의 사람과 일의 상태를 매칭시키며 메모이제이션을 적용하면 풀 수 있다. 점화식 || 외판원 문제와 점화식이 같다. 하지만 일을 배정하는데 순서는 관계 없으므로 그냥 단순히 차례대로 배정하며 메모이제이션을 적용해도 무리 없이 풀 수 있다. 코드 || 더보기 #include #i..