본문 바로가기

BOJ67

[BOJ] 백준 1956번: 운동 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 u를 완전탐색 O(n^3)로 구할 수 있습니다. 초기값을 입력 경로로 넣어주고 나머지는 꽤 큰값 (1e9)로 초기화한 뒤 3중 포문으로 구해 나가는 코드입니다. #include #include #include #include #include #include #include #include using namespace std; int n, m; int buf[401][401]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i a .. 2020. 8. 9.
[BOJ] 백준 9370번: 미확인 도착지 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 문제 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지�� www.acmicpc.net 시작점 s와 지나간 두 정점 g와 h의 정보, 전체 경로들에 대한 정보 및 목적지 후보 t가 주어질 때, 시작점에서 목적지까지 최단 경로가 시작점에서 g와 h를 잇는 간선을 지나 목적지까지 가는 최단경로의 비용이 같은 목적지 후보들을 찾는 문제입니다. 먼저 시작점에서 모든 정점까지 가는 최단 경로를 구합니다. 우선순위 큐를 사용한 다익스트라로 빠르게 구할 수 있습니다. (SPFA + SL.. 2020. 8. 9.
[BOJ] 백준 10217번: KCM Travel https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세�� www.acmicpc.net M원 이하로 1번 도시에서 N번 도시까지 갈 수 있는 경로 중 최단시간을 요구하는 문제입니다. 두가지 방법이 있는데 저는 동적계획법으로 해결했습니다. DP[i][j] 배열을 i 도시에서 j원으로 출발할 때 n 도시까지 걸리는 최단 시간으로 정의했습니다. 주의할 점은 입력 중 출발공항과 도착공항이 같은 여러개의 티켓 정보가 들어올 수 있다는 점입니다. (이걸.. 2020. 8. 9.
[BOJ] 백준 1700번: 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 요즘 그리디에 너무 약해서 그리디 문제를 풀던 중 골머리를 앓았던 문제에 대하여 포스팅합니다. 이 문제는 각 전기용품의 사용 순서가 k개 주어지고 멀티탭이 n개 구멍이 있을때 주어진 전기용품을 순서대로 사용하면서 플러그를 뽑는 최소횟수 구해야 합니다. 가장 처음에 든 생각은 멀티탭을 모두 사용하고 있으며 다음 전기용품이 멀티탭에 꼽혀있지 않은 경우, 즉 플러그를 하나 뽑아야되는 시점에서, 꼽혀있는.. 2020. 8. 7.

티스토리툴바