https://www.acmicpc.net/problem/4011 4011번: 기름 파기 첫 번째 줄에는 세 개의 정수 M, N, K가 주어지는데, M과 N은 각각 직사각형 격자의 행과 열 개수이고 K는 한 사업자가 입찰에 응할 수 있는 정사각형 구역 한 변의 크기이다. 다음 M개의 줄에는 각 www.acmicpc.net 구역을 최대 3개만 팔 수 있기 때문에 여러가지 경우를 구상해 볼 수 있다. 총 6가지 경우가 있다. 왼쪽 위에서 부터 시작하는 DP, 오른쪽 위에서 부터 시작하는 DP, 왼쪽 아래에서 부터 시작하는 DP, 오른쪽 아래에서 부터 시작하는 DP테이블을 만든다. DP테이블의 정의는 \(dp[i][j]\) : 시작점부터 \((i,j\))까지 의 영역에서 기름을 파낼 한 구간을 구할 때 최대 ..
https://www.acmicpc.net/problem/1665 1665번: 화물열차 첫째 줄에는 화물 열차 A에 연속적으로 컨테이너가 놓여 있는 구간의 개수 N이 주어진다. 이어 N줄에는 Xi와 Yi (Xi ≤ Yi)가 공백을 사이에 두고 주어지는데 이는 화물 열차 A의 Xi칸부터 Yi칸까지 컨 www.acmicpc.net 이렇게 총 5개의 상황이 벌어질 수 있고, 두 시작점이 만나는 시점부터 컨테이너가 만나는 칸 수가 늘어나다가, A의 시작이 B의 끝을 만나거나, A의 끝이 B의 시작을 만나는 경우가 생기면 칸 수가 유지되다가 하락한다. 그러다 두 끝점이 만나는 시점부터는 컨테이너가 만나는 칸 수가 0이 유지된다. 이 기울기 함수들을 누적합으로 관리해서 최대로 컨테이너 끼리 만나는 칸 수가 몇인지 ..
https://www.acmicpc.net/problem/1616 1616번: 드럼통 메시지 첫째 줄에 자연수 K, M이 주어진다. K는 2이상, M은 1이상인 자연수이다. 항상 KM ≤ 10,000,000을 만족한다. www.acmicpc.net 일단 길이가 \(M-1\) 개로 이루어진 모든 메시지에 대해 다음 메시지로 나올 수 있는 메시지들에 대해 간선을 이어준다. 이때, 간선의 가중치에는 추가되는 수가 부여된다. 아래의 경우는 \(K = 2\), \(M = 3\) 인 경우다. 여기서 오일러 경로를 사용해 지나쳐온 모든 간선들의 가중치를 저장해둔다. 저장된 값은 \(11101000\)이고, 놀랍게도, 저장된 메시지는 우리가 찾고자 하는 답이 된다. 시간 복잡도는 \(O(K^{M-1}*K)\) = \(..
- Total
- Today
- Yesterday
- PS
- 알고리즘 문제 풀이
- 스택
- codeforces
- 1909
- 정렬
- 누적 합
- 간단한 풀이
- gunwookim
- 오일러 경로
- 세그먼트 트리
- 쿼리
- 비요뜨 존맛
- 냄새 싫어
- BOJ
- 수열과 쿼리
- 하이퍼
- AtCoder
- Offline Dynamic Connectivity
- Rabin-Karp
- hyper
- 앳코더
- combination
- 비요뜨
- DP
- Constructive
- ABC
- 김춘배
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |