문제풀이 썸네일형 리스트형 백준 16287 Parcel https://www.acmicpc.net/problem/16287 MITM? .. 모르겠다분할 정복으로 풀었다 4개를 고르는 경우를 모두 살펴야 하는데 $O(N^2)$까지 되는 제한이다.BOJ 9007 같은 느낌으로 일단 2개를 고르는 경우를 모두 구한 뒤 이를 잘 활용해 답을 구하고 싶어진다. $w$ 범위가 너무 크지 않으니 2개를 고르는 모든 경우에 대해 고른 두 수의 합을 인덱스로 사용하는 체크 배열을 만들면 합치는 과정은 $O(N^2)$ 정도에 할 수 있다. 2개를 고른 두 경우를 합칠 때 선택한 원소가 같으면 안 되니 배열을 반으로 나누어 한 쪽에서 2개, 다른 쪽에서 2개를 선택한다는 생각을 해볼 수 있다. 반으로 나누면 한 쪽에서 4개 모두 고르는 경우는 분할 정복처럼 처리할 수 있으니 .. 더보기 백준 10070 벽 https://www.acmicpc.net/problem/10070 구간에 min, max를 적용하는 쿼리를 처리하면 된다.구간 쿼리니까 세그 박고 싶은데 먼가 잘 안 되고..무지성으로 쓰자니 쿼리 순서에 따라 답이 달라지고..세그비츠가 비슷한 연산을 지원했던 것 같기도 하고..?뇌절하지 말자 lazy propagation을 설계할 때는 한 정점에 여러 쿼리가 쌓이는 상황을 잘 생각해야 한다.같은 구간에 적용된 쿼리 중 min 쿼리는 $h$가 최대인 것만, max 쿼리는 $h$가 최소인 것만 고려하면 된다는 점은 자명하다. 고려할 min 쿼리의 $h$를 $min_h$, max 쿼리의 $h$를 $max_h$로 두자.구간에 적용된 $min_h$ $\le$ $max_h$인 경우는 문제가 되지 않고, 크기가 뒤.. 더보기 백준 2673번 교차하지 않는 원의 현들의 최대집합 http://icpc.me/2673 2673번: 교차하지 않는 원의 현들의 최대집합 평면상에 있는 원의 둘레에 100개의 점이 일정한 간격으로 시계방향으로 번호가 1, 2, ... 100으로 붙여져 있다. 이 점들을 끝점으로 갖는 N개의 선분(원의 현)이 입력으로 주어질 때, 이들중에서 서 www.acmicpc.net 풀이 원의 현이라고 하면 되게 복잡해지고 풀기 싫어집니다. 하지만 두 현의 교차 여부만 중요하다는 점을 잘 생각해 보면 현을 수평선상의 구간으로 생각해도 문제가 없다는 것을 알 수 있습니다. 두 현의 교차하려면 각 현을 나타낸 두 구간이 겹치면서 한 구간이 다른 구간에 포함되지 않아야 합니다. 아래 그림은 예제를 구간으로 나타낸 모습입니다. 여기까지 왔으면 DP로 문제를 풀 수 있습니다. .. 더보기 ABC 228 E Integer Sequence Fair 풀이 오늘 대회 중에 아쉽게 못 풀었던 문제입니다. 페르마의 소정리를 안다면 어렵지 않게 풀 수 있고, 좋은 문제인지는 잘 모르겠지만 개인적으로 이 문제를 풀며 몇 가지를 배우게 되어 정리할 겸 풀이를 작성하려 합니다. 문제 https://atcoder.jp/contests/abc228/tasks/abc228_e E - Integer Sequence Fair AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 1 이상 K 이하의 자연수가 N개 있는 모든 배열에 1 이상 M 이하의 가치를 매기는 경우의 수를 $Q = 99824435.. 더보기 백준 17106번 빙고 http://icpc.me/17106 17106번: 빙고 한 줄에 5개의 글자, 총 5줄을 출력한다. 각 줄은 순서대로 빙고판의 각 행을 나타낸다. 색칠된 칸은 "#", 색칠되지 않은 칸은 "."로 따옴표 없이 나타낸다. 예를 들어 A1, C3, C4만 색칠하려면 다음과 www.acmicpc.net 풀이 25개의 빙고 칸 각각을 색칠하거나 색칠하지 않을 수 있으므로 빙고 칸을 채우는 경우의 수는 $2^{25}$가지입니다. 모든 경우를 살펴보며 각 경우의 수마다 모든 칸이 올바르게 색칠되었는지를 체크하는 코드를 작성하면 정답을 찾을 수 있습니다. 다소 문제가 되는 칸은 B5입니다. 다른 칸들은 모두 빙고판의 상태를 통해 올바르게 색칠되었는지 알 수 있지만 이 칸은 그렇지 않습니다. B5가 참이라고 가정하고.. 더보기 백준 4828번 XML http://icpc.me/4828 4828번: XML 인터넷프로그래밍 교수 이다솜은 XML이야말로 세상을 바꿀 혁신적인 언어라고 믿으며, 항상 학생들에게 XML의 장점을 어필한다. 그러나 잘못 사용되었다가는 지구를 파괴할 수도 있는 무시무시 www.acmicpc.net 풀이 코드를 한 글자씩 읽으며 현재 상태를 저장하는 열거형 변수 now의 값과 현재 글자에 따라 적절히 처리해주었습니다. 상태가 TAG이면 태그를, AMPERSAND이면 & 다음을 읽고 있다는 의미이며 둘 다 해당되지 않는 상태는 NORMAL으로 나타냅니다. 문제가 있는 코드를 만나면 상태를 ERROR로 지정하고 읽기를 중단합니다. 코드를 모두 읽은 후 context 스택이 비었는지, 아직 태그나 & 뒤를 읽고 있는지 여부를 추가적으로 .. 더보기 백준 20051번 Zagrade http://icpc.me/20051 20051번: Zagrade It is well known that the Central Intelligence Agency is tasked with gathering, processing and analyzing national security information. It is also suspected that they own quite large collections of commonly-used computer passwords and are developing some q www.acmicpc.net 문제 인터랙티브 문제입니다. 길이가 짝수인 정수 $N$이고 여는 괄호( '(' )와 닫는 괄호( '(' )의 개수가 같은 문자열이 있을 때, ? s e 쿼리로.. 더보기 백준 1071번 소트 http://icpc.me/1071 1071번: 소트 N개의 정수가 주어지면, 이것을 연속된 두 수가 연속된 값이 아니게 정렬(A[i] + 1 ≠ A[i+1])하는 프로그램을 작성하시오. 가능한 것이 여러 가지라면 사전순으로 가장 앞서는 것을 출력한다. www.acmicpc.net 풀이 간단한 그리디 문제입니다. 사전순으로 앞선 배열을 만들어야 하기 때문에 앞에서 최대한 작은 수를 사용해야 합니다. 앞서 $i$개의 수를 최적으로 출력했다고 가정할 때 가능하다면 무조건 출력하지 않은 수 중 최솟값을 출력해야 하며, 최솟값을 출력할 수 없다면 두 번째로 작은 값을 출력해야 합니다. 최솟값을 출력할 수 없는 경우는 두 가지입니다. 1) $i$번째로 출력한 수 + 1 == 최솟값일 때 2) 출력하지 않은 수에서.. 더보기 이전 1 2 3 다음
