본문 바로가기

전체 글

BOJ 14181 - 함수와 쿼리 (D3) CHT 처음 배울때 봤다가 이게 왜 CHT지 하고 탈주했다. http://boj.kr/14181 14181번: 함수와 쿼리 첫째 줄에 배열 a의 크기 n (1 ≤ n ≤ 105)가 주어지고, 둘째 줄에 배열 a[1], a[2], ..., a[n]이 주어진다. (0 ≤ a[i] ≤ 104) 다음 줄에는 쿼리의 개수 m (1 ≤ m ≤ 105)가 주어지고, 다음 m개의 줄에는 쿼리 www.acmicpc.net 풀이) Li-chao + Segment Tree 점화식을 세우기 영 쉽지 않아 보인다. 그러므로 정의에 따라 점화식을 관찰하자. $$ f(1,j)=a[j] $$ $$ f(2,j) = min (f(1,j), f(1,j-1)) + a[j] $$ $$ = min(2*a[j], a[j-1] + a[j]) $$.. 더보기
BOJ 3319 - 전령들 (D3) http://boj.kr/3319 #CHT #LiChaoTree #rollback 첫 D3이자 첫 자력솔 D3이다. 그런데 구현을 곁들인 3319번: 전령들 옛날 옛날에, 아름다운 몰다비아의 지역에 1부터 N까지 고유한 번호가 붙여진 N개의 중세 도시가 있었다. 번호 1이 붙여진 도시는 수도이다. 도시들은 N-1개의 양방향 도로로 연결되어 있으며, 각 www.acmicpc.net convex hull trick (by li chao tree) + rollback 풀이가 선뜻 생각나지 않는 이유는, 트리에서 CHT를 해야하기 때문이다. 그래도 일단 dp 식을 세워보자. dp[i] := i번에서 1번까지 가는데 걸리는 최소 시간 i에서 1번으로 갈때는, i -> 1 경로 사이에 있는 어떠한 정점 j에 대하여.. 더보기
골드 그리디 랜덤 (2) 오늘도 열심히 그리디를 하자. 1. BOJ 2759 - 팬케이크 뒤집기 (G4) http://boj.kr/2759 2759번: 팬케이크 뒤집기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 숫자 여러개가 공백으로 구분되어있다. 첫 번째 숫자는 팬케이크의 개수 N이고, 그 다음 N개의 숫자는 팬케이크의 크기이다. www.acmicpc.net sol) constructive(그리디 스타일) 자명하게도 n번 팬케이크가 n번 위치에 있지 않으면 반드시 n번 팬케이크를 1번으로 옮긴 후, n번으로 옮겨야 한다. 이렇게 옮기고 나면 n-1번 팬케이크가 n-1번 위치에 있는지 판별하는 문제로 바뀐다. 위 과정을 계속 반복하면 된다. 이때 1번 위치에서는 뒤집어도 상태가 똑같으므로 굳이 뒤집을 필.. 더보기
골드 그리디 랜덤 (1) 그리디 연습이 좀 필요하다고 느껴서 랜덤으로 그리디 문제를 풀어봤다. 1. BOJ 20311 : 화학 실험 (G5) http://boj.kr/20311 20311번: 화학 실험 화학 실험을 하던 윤이는 일렬로 나열해 놓은 $N$개의 시험관에서 재밌는 특징을 발견했다. 그 특징은 모든 이웃한 시험관 쌍에 대해, 두 시험관에 들어 있는 시약의 색깔이 서로 다르다는 점이 www.acmicpc.net solve) 그리디(sort) + constructive 꽤나 직관적인 그리디 문제이다. 색깔 수가 많은 숫자부터 배치하는데, 앞쪽부터 1칸씩 띄워서 배치하면 된다. 이때 배치하다가 갯수가 부족하면 다음 색깔부터 이어서 배치하되, 다른 색깔은 인접해도 무방하므로 다음과 같이 배치한다. 예를 들어 1번 색과 2번 색.. 더보기
ABC306 결과 블루는 커녕 민트 복구도 못하게 생겼다. 근데 unrated??????? A - 0:00 ~ 0:40 그냥 구현. 바로 제출해서 맞았다. 풀이)문자열을 입력받고, 반복문으로 한 문자를 2번씩 출력하면 됩니다. ll n, m, q, k; string s,t; set st; int main(){ fast; cin>>n>>s; for(auto i : s)couta; v[a].push_back(i+1); } vector ans; for(int i = 1 ; i >b; memset(dp,-1,sizeof(dp)); coutn>>k>>q; for(int i = 0 ; i < k ; i++)s.insert(0); for(int i = 0 ; i < n-k ; i++)t.insert(0); while(q--){ .. 더보기
BOJ 18770 - 불안정한 물질 (P2) #dfs #tree-dp 구현이 짜증나는 문제다. 문제는 꽤 재밌는데, n개의 노드와 n개의 간선이 있다. 이상태에서 인접하지 않은 정점만 골라서 최대 점수를 얻는 문제다. 만약 n개의 노드가 다 연결되어 있다면 그 그래프는 트리에 하나의 간선을 추가한 형태일 것이고, 그 간선에 의해 indegree가 2인 정점이 생긴다. 그래서 이 정점과 그 부모를 골라내서 이 정점들끼리는 미리 고를지 말지를 결정해두고, 간선을 하나 지우면 트리가 된다. 그 이후로 트리 dp를 돌리면 된다. 과연 이게 가능할까? 생각해보면 트리에서 간선만 하나 추가한 형태이기 때문에, 고려할 정점은 무조건 3개이다. 그래서 이 3개끼리 잘 케이스를 나눠가면서 연결그래프를 유지하되 간선을 하나 지울 수 있다. 그러면 트리가 되므로 .. 더보기
BOJ 1739 - 도로 정비하기 티어: D5 (체감 D5) 알고리즘: 2-SAT 여기서는 가로 도로를 행, 세로 도로를 열로 표기한다. 어떤 버스가 (a,b)에서 (c,d)로 갈려면 다음 2가지 중 하나를 이용해야 한다. (도로를 최대 2개밖에 이용하지 못하기 때문) 1. a행, d열을 이용한다. 2. c행, b열을 이용한다. 일단 a≠c, b≠d라고 가정하고 예제 1의 테스트케이스 1을 보자. 위 그림은 테스트케이스 1번에서 (1,1)에서 (6,6)으로 가는 버스를 나타낸 것이다. 빨간색 경로는 1행과 6열을 이용해서 (1,1)에서 (6,6)으로 간다. 파란색 경로는 1열과 6행을 이용해서 (1,1)에서 (6,6)으로 간다. 위를 통해 (a,b)에서 (c,d)로 갈려면 a행, d열을 이용하거나 c행, b열을 이용해야 함을 알 수 있다.. 더보기

티스토리툴바