본문 바로가기

DP

[BOJ] 백준 4883번 삼각 그래프 (Java)
Dot Algo∙ DS/PS 2021. 7. 14. [BOJ] 백준 4883번 삼각 그래프 (Java) #4883 삼각 그래프 난이도 : 실버 1 유형 : DP 4883번: 삼각 그래프 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 www.acmicpc.net ▸ 문제 이 문제는 삼각 그래프의 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 가는 최단 경로를 찾는 문제이다. 삼각 그래프는 사이클이 없는 그래프로 N ≥ 2 개의 행과 3열로 이루어져 있다. 삼각 그래프는 보통 그래프와 다르게 간선이 아닌 정점에 비용이 있다. 어떤 경로의 비용은 그 경로에서 지나간 정점의 비용의 합이다. 오른쪽 그림은 N = 4인 삼각 그래프이고, 가장 위쪽..
[BOJ] 백준 17069번 파이프 옮기기 2 (Java)
Dot Algo∙ DS/PS 2021. 6. 17. [BOJ] 백준 17069번 파이프 옮기기 2 (Java) #17069 파이프 옮기기 2 난이도 : 골드 5 유형 : DP 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net ▸ 문제 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형..
[BOJ] 백준 2098번 외판원 순회 (Java)
Dot Algo∙ DS/PS 2021. 6. 15. [BOJ] 백준 2098번 외판원 순회 (Java) #2098 외판원 순회 난이도 : 골드 1 유형 : DP/ 비트마스킹 / TSP 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net ▸ 문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 ..
[BOJ] 백준 1563번 개근상 (Java)
Dot Algo∙ DS/PS 2021. 6. 14. [BOJ] 백준 1563번 개근상 (Java) #1563 개근상 난이도 : 골드 4 유형 : DP 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net ▸ 문제 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독특하다. 출결사항이 기록되는 출결은 출석, 지각, 결석이다. 개근상을 받을 수 없는 사람은 지각을 두 번 이상 했거나, 결석을 세 번 연속으로 한 사람이다. 한 학기가 4일이고, O를 출석, L을 지각, A를 결석이라고 했을 때, 개..
[BOJ] 백준 2228번 구간 나누기 (Java)
Dot Algo∙ DS/PS 2021. 6. 9. [BOJ] 백준 2228번 구간 나누기 (Java) #2228 구간 나누기 난이도 : 골드 5 유형 : DP / 누적합 2228번: 구간 나누기 N(1≤N≤100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1≤M≤⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 www.acmicpc.net ▸ 문제 N(1≤N≤100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1≤M≤⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 한다. 각 구간은 한 개 이상의 연속된 수들로 이루어진다. 서로 다른 두 구간끼리 겹쳐있거나 인접해 있어서는 안 된다. 정확히 M개의 구간이 있어야 한다. M개 미만이..
[BOJ] 백준 13302번 리조트 (Java)
Dot Algo∙ DS/PS 2021. 6. 8. [BOJ] 백준 13302번 리조트 (Java) #13302 리조트 난이도 : 골드 5 유형 : DP 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net ▸ 문제 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 즐기기 위해서는 하루로는 터무니없이 부족하다. 그래서 많은 이용객들은 3일 이상 연속으로 이용하기도 한다. KOI 리조트에서는 3일 연속 이용권을 할인된 가격 이만오천원에, 연속 5일권은 삼만칠천원에 판매하고 있다. 게다가 연속..
[BOJ] 백준 2342번 Dance Dance Revolution (Java)
Dot Algo∙ DS/PS 2021. 6. 8. [BOJ] 백준 2342번 Dance Dance Revolution (Java) #2342 Dance Dance Revolution 난이도 : 골드 3 유형 : DP 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net ▸ 문제 승환이는 요즘 "Dance Dance Revolution"이라는 게임에 빠져 살고 있다. 하지만 그의 춤 솜씨를 보면 알 수 있듯이, 그는 DDR을 잘 하지 못한다. 그럼에도 불구하고 그는 살을 뺄 수 있다는 일념으로 DDR을 즐긴다. DDR은 아래의 그림과 같은 모양의 발판이 있고, 주어진 스텝에 맞춰 나가는 게임이다. 발판은 하나의..
[BOJ] 백준 2666번 벽장문의 이동 (Java)
Dot Algo∙ DS/PS 2021. 6. 7. [BOJ] 백준 2666번 벽장문의 이동 (Java) #2666 벽장문의 이동 난이도 : 골드 5 유형 : DP 2666번: 벽장문의 이동 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들 www.acmicpc.net ▸ 문제 n개의 같은 크기의 벽장들이 일렬로 붙어져 있고 벽장의 문은 n-2개만이 있다. 한 벽장 앞에 있는 문은 이웃 벽장 앞에 문이 없다면(즉, 벽장이 열려있다면) 그 벽장 앞으로 움직일 수 있다. 그림은 7개의 벽장의 예이다. 그림에서 2번 벽장과 5번 벽장이 열려있고, 나머지 벽장은 닫혀 있다. 벽장 문은 좌우 어느 쪽이든 그 이웃 벽장이 열려 있다면 그 쪽으로 한 칸씩 이동할 수 있다. 그림..

티스토리툴바

티스토리툴바