정올 (4) 썸네일형 리스트형 [BOJ 1725] 히스토그램 https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net Tag : DSU 풀이 히스토그램은 모노톤 큐, 분할정복, 세그먼트 트리 풀이가 있다는 것이 잘 알려진 문제입니다. 이 히스토그램을 유니온 파인드로도 풀 수 있는데 저는 이 풀이가 가장 쉽고 구현도 편한다고 생각합니다. 일단 (a[i], i)를 관리하는 벡터 v를 만들고 이를 내림차순으로 정렬합니다. 그리고 이를 순회하며 a[i - 1], a[i + 1]을 보며 a[i.. [BOJ 21817] 포항항 https://www.acmicpc.net/problem/23817 23817번: 포항항 첫번째 예제의 경우 오른쪽 3칸, 왼쪽 1칸, 아래쪽 3칸, 오른쪽 1칸, 왼쪽 3칸으로 총 11칸 이동하여 5개의 식당을 방문할 수 있다. 두번째 예제의 경우 장애물에 가로막혀 5개의 식당을 방문할 수 www.acmicpc.net Tag : bfs 문제요약 2차원 격자에 시작점, 식당의 위치가 표기되어있다. 식당 중 5개를 골라 방문하는 최단거리를 구하라. 풀이 이 문제 너무한다. 나는 맵에 식당이 5개만 있는 줄 알았지... K = 식당의 개수 일 때 벡터에 K - 5개의 0과 5개의 1을 넣어서 next permutation을 돌리면 방문할 식당 5개가 골라진다. 중복된 원소의 개수 때문에 이는 실제로 \(O(.. [BOJ 18313] Cave Paintings https://www.acmicpc.net/problem/18313 18313번: Cave Paintings Bessie has become an artist and is creating paintings of caves! Her current work in progress is a grid of height $N$ such that each row of the grid contains exactly $M$ squares ($1\le N,M\le 1000$). Each square is either empty, filled with rock, or filled www.acmicpc.net Tag : DSU, Tree DP 문제요약 이차원 격자에서 서로 다른 칸 a,b가 min(a의 높이, b의 높이)인 .. [BOJ 11001] 김치 https://www.acmicpc.net/problem/11001 11001번: 김치 첫 번째 줄에 날짜의 수와 시간 제한 N, D가 주어진다. (1 ≤ D ≤ N ≤ 100,000) 두 번째 줄에 온도 Ti가 주어진다. N-1 이하의 정수 i에 대해서 Ti >= Ti+1을 만족하며, 109 이하의 자연수이다. 세 번째 줄에 www.acmicpc.net Tag : dnc opt 문제요약 (숙성시간)*(꺼낼 때의 온도)+(넣은 날의 가치)의 최대를 구하는 문제다. \(D_i:=i\)일에 넣었을 때 최대"라 정의하고 문제가 요구하는 대로 식을 세우면 \(D_i=max_{iP(i+1)\)에 모순된다. 따라서 \(P(i)\leq P(i+1)\)이다. (그냥 monge array인거 보이는게 낫다) + 맞은사람.. 이전 1 다음
