동적 계획법 사다리

채점 가능한 DP 문제를 쉬운 순서로 모았습니다.

전체 결과문제 3128개

		유형				채점
강하게 매칭 가능한 그래프짝수 개의 정점을 가진 그래프가 모든 균형 이분할에 대해 완전 이분 매칭을 가지는지 판별한다.	어려움9	그래프수학+2	아직 제출이 없습니다	3초	512 MB	채점 가능
타일 배치높이가 같은 볼록 타일 14개 이하가 주어질 때, 잘린 모서리를 고려해 겹치지 않게 나란히 배치했을 때 필요한 프레임의 최소 너비를 구한다.	어려움9	동적 계획법기하+2	아직 제출이 없습니다	1초	1024 MB	채점 가능
크레이터원형 폭파구 n개의 중심과 반지름이 주어질 때, 모든 폭파구에서 10야드 이상 떨어진 하나의 닫힌 울타리의 최소 길이를 구한다.	어려움9	기하동적 계획법+2	아직 제출이 없습니다	2초	512 MB	채점 가능
흥이 오르는 점수 발표합이 x인 양의 추가 점수를 오름차순으로 발표할 때 매번 선두가 바뀌어야 한다는 조건에서 만들 수 있는 서로 다른 최종 순위의 수를 센다.	어려움9	동적 계획법조합론+2	아직 제출이 없습니다	2초	512 MB	채점 가능
보물 지도가중 무방향 그래프에서 각 광산의 채굴량이 날마다 줄어들며, 1번 광산에서 시작해 매일 이동해야 할 때 모을 수 있는 최대 금의 양을 구한다.	어려움9	그래프동적 계획법+2	아직 제출이 없습니다	2초	512 MB	채점 가능
Intuidiff첫 번째 문자열의 부분 문자열이거나 새 문자 한 개인 블록들을 이어 붙여 두 번째 문자열을 만들 때 필요한 최소 블록 수를 구한다.	어려움9	문자열 매칭그리디+2	아직 제출이 없습니다	7초	512 MB	채점 가능
학습지 알고리즘N개 정점 위의 무방향 그래프 X 중 G(P)=X를 만족하는 순열 P의 개수가 l 이상 r 이하인 것의 수를 1e9+7로 나눈 나머지로 구한다.	어려움9	조합론그래프+2	아직 제출이 없습니다	1초	512 MB	채점 가능
차고점 갱신이 있는 수열에서 각 구간 질의마다 모든 원소의 최대공약수가 1보다 큰 부분 배열의 개수를 센다.	어려움9	세그먼트 트리정수론+2	아직 제출이 없습니다	4초	256 MB	채점 가능
우두머리동물들이 원을 이루어 진행 중인 수를 1부터 K만큼 키우며, M을 말한 팀이 지는 게임에서 각 시작 위치마다 어느 팀이 이기는지 구한다.	어려움9	게임 이론동적 계획법+2	아직 제출이 없습니다	3초	512 MB	채점 가능
이멜다의 구두 쇼핑구간 더하기와 구간 뒤집기 연산이 가해지는 가격 배열에서, 매 연산 직후 값이 순증가하는 연속 구간의 개수를 출력한다.	어려움9	세그먼트 트리배열+2	아직 제출이 없습니다	5초	512 MB	채점 가능
캔디 꼬치주어진 알파벳으로 만든 길이 K 문자열 중 b>e 형태의 부분 문자열 함의 규칙을 모두 만족하는 문자열의 개수를 10^7로 나눈 나머지를 구한다.	어려움9	동적 계획법문자열+2	아직 제출이 없습니다	5초	512 MB	채점 가능
드라마H행 N열 격자에 검은 칸이 정확히 N개인 피라미드 색칠의 수를 10^9+7로 나눈 나머지를 구한다.	어려움9	조합론동적 계획법+1	아직 제출이 없습니다	2초	512 MB	채점 가능
끝나지 않는 BFS의 역습방문 처리를 빠뜨린 잘못된 BFS가 주어진 방향 그래프에서 유한 번에 멈추는지 판정하고, 멈춘다면 반복 횟수를 1e9+7로 나눈 값을 구한다.	어려움9	그래프BFS+2	아직 제출이 없습니다	2초	512 MB	채점 가능
컨베이어 벨트배송 요청 (a, b, p)이 하나씩 추가될 때마다, 초당 접시가 하나씩 도착하고 접시마다 제품 하나를 실을 수 있다는 조건에서 모든 작업을 끝내는 최소 시간을 구한다.	어려움9	수학그리디+2	아직 제출이 없습니다	2초	512 MB	채점 가능
배관공과 사나운 개홀수 행과 열에만 집이 있는 격자에서 각 집을 한 번씩 지나는 하강 경로들로 덮되, 개가 있는 칸을 지나는 파이프 비용을 최소화하고 경로 수를 K 이하로 제한하는 문제.	어려움9	동적 계획법그리디+2	아직 제출이 없습니다	2초	512 MB	채점 가능
블록 2N x M 직사각형을 1 x N부터 N x N까지의 블록으로 빈틈없이 채우는 방법의 수를 1999로 나눈 나머지를 구한다. M은 10^10까지 커질 수 있다.	어려움9	조합론동적 계획법+2	아직 제출이 없습니다	1초	256 MB	채점 가능
도장 찍기너비 K인 색 도장을 N칸 캔버스에 찍어 모든 칸이 칠해지도록 만들 때 가능한 서로 다른 그림의 수를 1e9+7로 나눈 나머지로 구한다.	어려움9	동적 계획법조합론+1	아직 제출이 없습니다	2초	512 MB	채점 가능
다각형의 최대 밝기볼록 다각형과 꼭짓점 삭제 순서가 주어질 때, 각 삭제 뒤 외부의 한 점이 비출 수 있는 변 길이 합의 최댓값을 구한다.	어려움9	기하동적 계획법+2	아직 제출이 없습니다	3초	1024 MB	채점 가능
가로수두 가지 색으로 각 건물 앞에 나무를 심는 최소 비용 배정을 유지하면서, 같음/다름 제약과 비용 갱신이 추가될 때마다 최적 비용을 출력한다.	어려움9	유니온 파인드그래프+2	아직 제출이 없습니다	2초	256 MB	채점 가능
수열의 개수주어진 N과 C에 대해 OR이 X, AND가 Y, XOR이 Z인 31비트 정수 N개 순서쌍의 수가 정확히 C가 되는 사전순 최소 (X, Y, Z)를 구하거나 존재하지 않으면 -1을 출력한다.	어려움9	비트 연산조합론+2	아직 제출이 없습니다	1초	128 MB	채점 가능
교차하지 않는 나이트 투어m×n 판(m은 8 이하, n은 10^15 이하)에서 자기 경로를 교차하지 않는 닫힌 나이트 투어가 방문할 수 있는 칸 수의 최댓값을 구한다.	어려움9	그리디동적 계획법+2	아직 제출이 없습니다	2초	1024 MB	채점 가능
일반 그래프 최대 가중치 매칭가중 무방향 그래프가 주어졌을 때, 간선 가중치 합이 최대인 매칭을 찾는다.	어려움9	그래프그리디+1	아직 제출이 없습니다	2초	512 MB	채점 가능
유라시아 합중국x좌표 순으로 정렬한 N개의 점을 최대 K개의 연속한 구역으로 나누어, 각 구역의 가장 먼 두 점 거리 제곱의 최댓값을 최소화한다.	어려움9	이분 탐색동적 계획법+2	아직 제출이 없습니다	20초	1024 MB	채점 가능
Xtreme NP-hard Problem?!정점 1에서 n까지 정확히 k개의 간선을 쓰는 단순 경로 중 가중치 합이 최소인 것을 찾고, 없으면 -1을 출력한다. n, m, k가 10^6까지 커서 문제 자체가 NP-난해임을 명시한다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	5초	1024 MB	채점 가능
떠돌이 상인가중치가 있는 방향 그래프와 각 시장의 K개 품목 매매 가격이 주어질 때, 한 번에 한 품목만 거래하며 닫힌 보행을 돌 때 이익을 시간으로 나눈 값의 최댓값을 구해 내림한 정수를 출력한다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	2초	512 MB	채점 가능
나무 탈출루트가 있는 트리에서 각 리프에 말이 하나씩 놓인 상태로 시작해, 두 사람이 번갈아 말을 부모로 옮기고 루트에 닿으면 제거하는 게임에서 선수가 이길 수 있는지 판정한다.	어려움9	게임 이론트리+2	아직 제출이 없습니다	2초	512 MB	채점 가능
피보나치 자릿수1, 2, 3, ...을 피보나치 수 체계로 이어 붙인 무한 문자열의 앞 N개 문자 안에 부분 문자열 "11"이 몇 번 나타나는지 센다.	어려움9	수학동적 계획법+2	아직 제출이 없습니다	2초	1024 MB	채점 가능
로고3x3 격자에서 잘라낸 최대 5가지 조각(회전과 뒤집기 가능)과 최대 3개의 55x5 이하 격자 디자인이 주어질 때, 각 디자인을 겹치지 않는 조각으로 정확히 덮을 수 있는지 판정하고 최소 조각 수를 구하거나 NIE를 출력한다.	어려움10	동적 계획법비트 연산+2	아직 제출이 없습니다	1초	128 MB	채점 가능