백준 13489번 Vještica
단어 집합을 비트마스크로 나누고 공통 prefix를 최대한 겹쳐 Trie 노드 수를 최소로 만드는 DP
모든 태그
주제
#dp
글 46개
-
-
백준 24229번 모두싸인 출근길
판자를 정렬하고 겹치는 판자를 이어 붙인 구간으로 갈 수 있는 최종 위치 계산하기
-
백준 25949번 Jar Game
세 항아리에 남은 조약돌 수와 현재 턴을 상태로 둔 게임 DP로 승패 판정하기
-
백준 2287번 모노디지털 표현
숫자를 i개, j개 써서 만든 값끼리 사칙연산으로 합쳐 i+j개의 값 집합을 만드는 DP
-
백준 1086번 박성원
고른 숫자 집합과 현재 나머지를 상태로 두고, 큰 수 대신 나머지만 이어 붙이는 비트마스크 DP
-
백준 2618번 경찰차
두 경찰차가 마지막으로 맡은 사건 번호를 상태로 둔 DP와 어느 차가 맡았는지 역추적하기
-
백준 1014번 컨닝
윗줄의 앉은 상태를 비트마스크로 두고 행 단위로 내려가며 최대 인원을 메모이제이션하는 DP
-
백준 22871번 징검다리 건너기 (large)
중간 돌을 거치는 비용 중 큰 값을 다시 최소로 만드는 DP, int 범위 주의
-
백준 2152번 여행 계획 세우기
SCC로 압축한 그래프에서 시작점에서 닿는 컴포넌트만 따라가며 방문 도시 수 최대화하기
-
백준 4013번 ATM
SCC로 압축한 DAG에서 시작 SCC에서 닿는 경로만 따라가며 최대 현금을 구하는 DP
-
백준 2637번 장난감 조립
위상 정렬 순서로 중간 부품의 기본 부품 필요량을 곱해 누적하기, 역추적으로 난 메모리 초과
-
백준 2213번 트리의 독립집합
부모 선택 여부에 따라 현재 노드를 고를지 나누는 트리 DP와 선택된 노드 복원
-
백준 2248번 이진수 찾기
자릿수와 1의 개수 제한별 경우의 수를 DP로 세고 앞자리부터 I번째 수를 만들어 가기
-
백준 2533번 사회망 서비스
부모가 얼리어답터인지에 따라 현재 노드의 선택지를 나누는 트리 DP
-
백준 14003번 가장 긴 증가하는 부분 수열 5
O(N log N) LIS를 구하며 값이 갱신될 때마다 이전 원소를 기록해 실제 수열을 복원하는 방법
-
백준 10942번 팰린드롬?
양 끝 문자가 같고 안쪽 구간이 팰린드롬이면 전체도 팰린드롬이라는 점화식으로 여러 질의 처리
-
백준 1509번 팰린드롬 분할
팰린드롬 구간 판정 DP 위에 최소 분할 수 DP를 하나 더 쌓아 시간 초과 피하기
-
백준 2342번 Dance Dance Revolution
양발 위치와 진행 순서를 상태로 두고 최소 힘을 메모이제이션하는 DP
-
백준 7579번 앱
메모리 대신 비용을 인덱스로 두고 비용별 최대 확보 메모리를 저장하는 배낭 DP
-
백준 11049번 행렬 곱셈 순서
시작과 끝 행렬 구간을 상태로 두고 나누는 지점마다 곱셈 비용의 최솟값을 구하는 구간 DP
-
백준 17404번 RGB거리 2
첫 집의 색을 고정하고 마지막 집이 그 색과 겹치지 않게 하는 원형 RGB 거리 DP
-
백준 10649번 프리스비
고른 소 집합의 최대 안정도를 비트마스크 DP로 기록하고 새 소를 위나 아래에 놓는 경우 비교
-
백준 1176번 섞기
마지막으로 세운 학생과 지금까지 세운 학생 집합을 상태로 둔 비트마스크 DP, int 범위 초과 주의
-
백준 1029번 그림 교환
현재 소유자, 구매 가격, 거쳐 간 예술가 집합을 상태로 둔 비트마스크 DP와 문제를 잘못 읽은 실수
-
백준 1480번 보석 모으기
가방 번호, 현재 가방 무게, 담은 보석 집합을 상태로 둔 비트마스크 DP
-
백준 16991번 외판원 순회 3
좌표 사이 유클리드 거리를 비용으로 쓰는 비트마스크 TSP, 소수점 출력 주의
-
백준 2320번 끝말잇기
마지막 글자와 사용한 단어 집합을 상태로 둔 비트마스크 DP로 최고 점수 구하기
-
백준 1102번 발전소
켜진 발전소를 비트마스크로 두고 P개 이상 켜는 최소 비용을 메모이제이션하는 탑다운 DP
-
백준 3056번 007
배정한 미션을 비트마스크로 두고 요원 순서대로 최대 성공 확률을 구하는 DP
-
백준 2098번 외판원 순회
현재 도시와 방문한 도시 비트마스크를 상태로 둔 외판원 순회 DP
-
백준 1562번 계단 수
길이, 마지막 숫자, 지금까지 쓴 숫자 비트마스크를 상태로 0~9를 모두 쓰는 계단 수 세기
-
백준 2096번 내려가기
직전 줄의 최댓값과 최솟값만 남기는 DP로 4MB 메모리 제한 통과하기
-
백준 2294번 동전 2
금액별 최소 동전 수를 저장하는 DP, INT_MAX에 1을 더해 INT_MIN이 된 실수
-
백준 9251번 LCS
두 문자열의 접두사 쌍마다 최장 공통 부분 수열 길이를 저장하는 2차원 DP
-
백준 2407번 조합
파스칼의 삼각형 점화식으로 큰 조합 값을 직접 계산하기
-
백준 9465번 스티커
두 줄 DP 테이블에 각 스티커를 골랐을 때의 최대 점수를 대각선 방향으로 누적하기
-
백준 12865번 평범한 배낭
무게별 최대 가치를 저장하는 DP 테이블로 완전 탐색 없이 푸는 0/1 배낭 문제
-
백준 11660번 구간 합 구하기 5
행과 열 방향으로 누적한 2차원 누적합에서 포함-배제로 직사각형 합 구하기
-
백준 1932번 정수 삼각형
왼쪽 위와 오른쪽 위 중 큰 합을 고르며 내려가는 정수 삼각형 DP
-
백준 2579번 계단 오르기
세 계단 연속 금지와 마지막 계단 필수 조건을 두 가지 이전 상태로 처리하는 DP
-
백준 11726번 2xn 타일링
마지막에 세로 타일 하나를 붙이는 경우와 가로 타일 두 개를 붙이는 경우를 더하는 점화식
-
백준 12015번 가장 긴 증가하는 부분 수열 2
길이별로 가장 작은 끝값을 유지하고 이분 탐색으로 갱신하는 O(N log N) LIS
-
백준 11053번 가장 긴 증가하는 부분 수열
각 원소를 끝으로 하는 LIS 길이를 앞의 원소들과 비교해 갱신하는 O(N²) DP와 그 한계
-
백준 1912번 연속합
누적합이 음수가 되면 다음 원소에서 새로 시작하는 카데인 알고리즘
-
백준 2293번 동전 1
동전을 하나씩 추가하며 금액별 경우의 수를 갱신하는 d2[i] = d1[i] + d2[i-v] 점화식
-
백준 1149번 RGB거리
이전 집을 다른 색으로 칠한 최소 비용 중 작은 쪽을 고르는 RGB 거리 DP 점화식