쉽지않은 블로그

https://www.acmicpc.net/problem/13209 13209번: 검역소 3번 도시와 5번 도시를 잇는 도로와 4번 도시와 3번 도시를 잇는 도로에 검역소를 설치하면 치료제를 11 인분만 비축해도 된다. 1번 도시에 전염병이 발생할 경우 1번 도시와 3번 도시의 10명의 사 www.acmicpc.net 나의 풀이 이 문제는 간단하게 말하면 트리구조의 자료구조에서 각 집 단안의 모든 노드 값의 합중 최댓값이 최소가 되게끔 집합을 묶었을 경우 집단내의 노드합이 최대값이 얼마인지를 묻는 문제이다. 이 문제는 10만개의 노드들을 어떻게 묶을지 선택을 해야 하는데 순차적으로 포함 여부를 모두 해보면 당연히 시간 초과가 날것이다 그리디나 DP 로 생각을 해보려고 했지만 하나를 선택함으로써 나머지가 ..

www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 나의 풀이 사실 이문제는 이문제의 제작자인 데구리형님 에게 약간의 힌트를 예전에 들은적이 있어 그 기억을 더듬어보며 바로 문제를 풀수 있었다. 이 문제는 단방향인게 골때리는 점이다. 이 문제가 양방향이 였다면 면접장을 기준으로 다익스트라를 돌려보면 모든 마을의 최단거리를 저장하고 모든 마을의 최단거리중 가장 큰 값을 정답의 후보로 올려주면 되는문제였을것이다..

www.acmicpc.net/problem/17831 17831번: 대기업 승범이네 첫 번째 줄에 판매원들의 수 N(2 ≤ N ≤ 200,000)이 주어진다. 판매원들은 1번, 2번, …, N번으로 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 2번 판매원부터 N번 판매원의 사수가 순서대 www.acmicpc.net 나의 풀이 이 문제는 그리디 하게 풀 수 없다 어느 사원이 속하냐 안 속하냐는 다른 사원들의 값에도 효과를 미치기 때문에 방향을 고려하여 문제를 풀어야 된다 트리로 되어있는 문제이기때문에 맨 아래 리프 노드 푸터 루트 노드까지 쭉 뭔가 정보를 가지고 올려다 주면 위에서 판별할 수 있지 않을까 생각을 하였다 그리고 자료구조를 구성하자면 $dp[i][2]$ 를 로 생각을 해볼 수..

www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 나의 풀이 처음에는 set으로 풀어도 TLE를 당하지 않으리라는 생각으로 제출했지만 시간 초과가 났었다... 트라이로 풀어야 겠다는 생각을 했지만 트라이를 무조건? 써야 될 것 같진 않아서 생각을 하다 보니 힌트를 얻었다. 만약 전화번호 목록이 139 2321 12323 1392 다음과 같이 구성이 되어있다고 생각하면 문자열 전체를 보지 말고 모든 문자열을 사전순으로 정렬을 해보면 139..

www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 www.acmicpc.net 나의 풀이 이문제는 DP로 푸는 방법을 생각해야 한다 DP로 생각할 수 있는 근거는 특정 상태 1번 경찰차가 움직였거나 2번 경찰차가 움직인 경우 두 가지밖에 없기 때문에 그 두가지 action에 따른 최소의 cost만 기억해주면 된다. (특정 상태에서 최솟값은 이전 상태의 최솟값을 이용해 구해야 되는 논리가 나오게 되므로) 두대의 경찰차에 대하여 주어진 좌표 순으로 사건을 해결해야 하므로 처음에는..

www.acmicpc.net/problem/2306 2306번: 유전자 DNA 서열은 4개의 문자 {a,c,g,t} 로 이루어진 문자열이다. DNA 서열에는 생명의 신비를 풀 수 있는 많은 정보가 들어 있다. 특히 KOI 유전자의 길이는 사람의 키와 깊은 상관 관계가 있다는 것이 알려 www.acmicpc.net 나의 풀이 최대 길이가 정의되는 경우는 1) KOI유전자 + KOI유전자 또는 2) KOI유전자 안에 KOI유전자 가 들어가 있는 구조이므로 최대길이를 구하려고 할 때는 작은 것부터 결과를 이끌어내는 다이내믹 프로그래밍으로 풀어야 된다고 생각했다. 입력으로 주어진 문자열을 S라고 할 경우 i

www.acmicpc.net/problem/1533 1533번: 길의 개수 첫째 줄에 교차점의 개수 N이 주어진다. N은 10보다 작거나 같고, 시작점의 위치 S와 끝점의 위치 E, 그리고 정문이가 늦는 시간 T도 주어진다. S와 E는 N보다 작거나 같은 자연수이다. T는 1,000,000,000 www.acmicpc.net 문제 요약 1. 입력 n(행렬의 사이즈) , T(시간) , S(시작점), E(끝 지점)과 행렬이 다음 입력으로 주어진다 2. 행렬의 정의가 matrix [i][j]가 0보다 같거나 크고 5 이하인 게 보장되고 그럴 경우 i에서 j로 가는데 걸린 시간을 표현 3.T시간 동안 S에서 E까지 갈 수 있는 경로의 가짓수를 1,000,003으로 나눈 나머지로 출력 나의 풀이 처음 이문제를 보..

www.acmicpc.net/problem/16287 16287번: Parcel 입력은 표준입력을 사용한다. 입력의 첫 줄에는 무게 w(10 ≤ w ≤ 799,994)와 A의 원소 개수 n(4 ≤ n ≤ 5,000)이 공백으로 분리되어 주어진다. 다음 줄에는 A의 원소인 n개의 정수 ai ∈ A(1 ≤ i ≤ n)가 www.acmicpc.net 문제요약 1.서로다른 N개의 정수가 주어졌을때 (4