본문 바로가기

BOJ

BOJ 18830 - 하이퍼 수열과 하이퍼 쿼리 (D5) PS를 진짜 제대로 하겠다는 마음가짐으로 역겨운 것도 다 풀기로 했다. 하이퍼 시리즈는 유명하다... 차원이 말도 안되게 큰 문제들이다. 얘는 이 문제를 11차원으로 늘린 문제이다. 그럼 그냥 11차원 prefix sum을 박으면 되느냐? 아쉽게도 아니다. prefix sum table을 채우는 원리는 포함-배제 원리이다. 이는 중복하여 더하고 빼는 구간들을 처리하는 것이다. 그래서 11차원 prefix sum을 채우려고 식을 세워보면 무려 2^11(=2048)개의 값을 더하고 빼는 형태가 나온다. 그래서 table을 채우는데에는 총 O(2^11 * nmopqrstuvw)가 나와 전체 서브태스크를 풀 수 없다. (아마 섭태3까지는 풀릴 것 같다.) 다행히도 얘를 O(11 * nmopqrstuvw)에 채울.. 더보기
solve G5~G1 (1) G5~G1 문제를 각각 1개씩 랜덤으로 풀어보기로 했다. 아래에 나오는 체감 티어는 주관이므로 신뢰하지 말자. (티어 옆에 +는 보통 그 티어의 난이도보다 어려웠단 뜻이고, -는 쉬웠단 뜻이다.) Gold 5 : Ordinary Ordinals (BOJ 24930) 풀이 : 수학(+분할정복 거듭제곱) 풀이 시간 : 약 10분 체감 티어 : Gold 5 문제를 이쁘게 정리하면 $$ A_{n} = 2A_{n-1} + 1 $$ 이 나온다. (단, A_0 = 2, A_1 = 4) 이제 점화식을 일반식으로 바꾸면 $$ A_{n} = 2^{n-1} A_{1} + 2^{n-1} - 1 $$ 이다. 2^(n-1)은 분할정복으로 O(logN)에 빠르게 구할 수 있으므로 O(logN)에 답을 구할 수 있다. using n.. 더보기
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 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열을 이용해야 함을 알 수 있다.. 더보기

티스토리툴바