본문 바로가기

DP

[BOJ] 백준 12888번 완전 이진 트리 도로 네트워크 (Java)
Dot Algo∙ DS/PS 2022. 3. 4. [BOJ] 백준 12888번 완전 이진 트리 도로 네트워크 (Java) #12888 완전 이진 트리 도로 네트워크 난이도 : 골드 4 유형 : dp / 트리 12888번: 완전 이진 트리 도로 네트워크 모든 도시를 방문한 차의 개수가 모두 1개가 되기 위해서, 수빈이가 차를 최소 몇 대를 보내야 하는지 출력한다. 정답은 항상 64비트 정수로 나타낼 수 있다. www.acmicpc.net ▸ 문제 BOJ 나라는 도시와 두 도시를 연결하는 도로로 이루어져 있다. 이 나라의 도로 네트워크는 완전 이진 트리의 형태를 가진다. 수빈이는 BOJ 나라의 도로 네트워크 트리의 높이 H를 알고 있다. 트리의 높이를 안다면, 도시의 개수와 도로의 개수도 구할 수 있다. 트리의 높이가 H인 경우에 도시의 개수는 2(H+1)-1개 이고, 도로의 개수는 2(H+1)-2개가 된다. 아래 그림은 H ..
[BOJ] 백준 3745번 오름세 (Java)
Dot Algo∙ DS/PS 2022. 2. 5. [BOJ] 백준 3745번 오름세 (Java) #3745 오름세 난이도 : 골드 2 유형 : LIS / DP / 이분 탐색 3745번: 오름세 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. www.acmicpc.net ▸ 문제 주식투자를 좋아하는 정인이는 주가의 오름세를 살펴보려고 한다. 정인이는 n일 동안 매일 주가를 적어놓았고, 여기서 오름세를 찾아보려고 한다. n일 동안의 주가를 p1, p2, ..., pn이라고 했을 때, 오름세란 부분수열 pi1 < pi2 < ... < pik (i1 < i2 < ... ik)을 말한다. n일 동안 주가가 주어졌을 때, 가장 긴 오름세를 찾는 프로그램을 작성..
[BOJ] 백준 8012번 한동이는 영업사원! (Java)
Dot Algo∙ DS/PS 2021. 12. 22. [BOJ] 백준 8012번 한동이는 영업사원! (Java) #8012 한동이는 영업사원! 난이도 : 플레 4 유형 : 트리 / LCA / DP 8012번: 한동이는 영업사원! 한동이는 경상도내를 돌아다니면서 열심히 일하는 영업사원이다. 예전에는 자기가 원하는 도시만 골라서 다닐 수 있었지만 시대가 바뀌어서 이제 그렇게는 하지 못하게 되었다. 시대가 바뀜에 www.acmicpc.net ▸ 문제 한동이는 경상도내를 돌아다니면서 열심히 일하는 영업사원이다. 예전에는 자기가 원하는 도시만 골라서 다닐 수 있었지만 시대가 바뀌어서 이제 그렇게는 하지 못하게 되었다. 시대가 바뀜에 따라, 한동이는 회사에서 돌아야 할 도시의 목록을 받고, 그 목록대로 도시를 여행한다. 회사에서 주는 여행지 목록은 정말 안타깝게도 최적화되어 있지가 않다. 여행을 떠나기 전에 한동이는 모든 도..
[BOJ] 백준 2352번 반도체 설계 (Java)
Dot Algo∙ DS/PS 2021. 11. 10. [BOJ] 백준 2352번 반도체 설계 (Java) #2352 반도체 설계 난이도 : 골드 2 유형 : 이진탐색/ DP 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net ▸ 문제 반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다. 예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지..
[BOJ] 백준 13511번 트리와 쿼리2 (Java)
Dot Algo∙ DS/PS 2021. 10. 19. [BOJ] 백준 13511번 트리와 쿼리2 (Java) #13511 트리와 쿼리2 난이도 : 플레 3 유형 : 트리 / LCA 13511번: 트리와 쿼리 2 N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 아래의 두 쿼리를 수행하 www.acmicpc.net ▸ 문제 N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 아래의 두 쿼리를 수행하는 프로그램을 작성하시오. 1 u v: u에서 v로 가는 경로의 비용을 출력한다. 2 u v k: u에서 v로 가는 경로에 존재하는 정점 중에서 k번째 정점을 출력한다. k는 u에서..
[BOJ] 백준 16437번 양 구출 작전 (Java)
Dot Algo∙ DS/PS 2021. 10. 4. [BOJ] 백준 16437번 양 구출 작전 (Java) #16437 양 구출 작전 난이도 : 골드 2 유형 : 트리 / DFS 16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net ▸ 문제 N개의 섬으로 이루어진 나라가 있습니다. 섬들은 1번 섬부터 N번 섬까지 있습니다. 1번 섬에는 구명보트만 있고 다른 섬에는 양들 또는 늑대들이 살고 있습니다. 늘어나는 늑대의 개체 수를 감당할 수 없던 양들은 구명보트를 타고 늑대가 없는 나라로 이주하기로 했습니다. 각 섬에서 1번 섬으로 가는 경로는 유일하며 i번 섬에는 pi번 섬으로 가는 다리가 있습니다. 양들은..
[BOJ] 백준 15681번 트리와 쿼리 (Java)
Dot Algo∙ DS/PS 2021. 10. 2. [BOJ] 백준 15681번 트리와 쿼리 (Java) #15681 트리와 쿼리 난이도 : 골드 5 유형 : 트리 순회 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net ▸ 문제 간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자. 정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다. 만약 이 문제를 해결하는 데에 어려움이 있다면, 하단의 힌트에 첨부한 문서를 참고하자. ▸ 입력 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (..
[BOJ] 백준 3176번 도시 네트워크 (Java)
Dot Algo∙ DS/PS 2021. 9. 21. [BOJ] 백준 3176번 도시 네트워크 (Java) #3176 도시 네트워크 난이도 : 플레 4 유형 : 트리 / LCA / DP 3176번: 도로 네트워크 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양 www.acmicpc.net ▸ 문제 N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다. 모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다. 총 K개의 도시 쌍이 주어진다. 이때, 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하는 프로그램을 작성하시오. ▸..

티스토리툴바

티스토리툴바