본문 바로가기

백준61

[UCPC] A번 전단지 돌리기, 백준 19542 https://www.acmicpc.net/problem/19542 19542번: 전단지 돌리기 현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민 www.acmicpc.net UCPC 본선 등록을 하지 못해서 본선이 끝난 뒤 공개된 문제를 풀어봤습니다. 트리를 탐색하면서 현재 노드에서 리프노드까지의 거리가 D이상인 자식노드로만 탐색하여 거리를 1씩 늘려 나가며, 왕복거리이기 때문에 거리에 2배를 해주시면 됩니다. #include #include #include #include #include #include #include using namespace std; typede.. 2020. 8. 6.
[BOJ] 백준 17367번: 공교육 도박 https://www.acmicpc.net/problem/17367 17367번: 공교육 도박 공교육의 수호자 수찬이는 공교육의 정수라고 할 수 있는 한국정보올림피아드의 문제를 가지고 게임을 하려고 한다. 수찬이는 2010년도 한국정보올림피아드 시·도 지역본선 중등부 1번 문제를 � www.acmicpc.net 주사위를 N번을 던져서 나온 최근 3개의 값으로 상금의 기대값을 구하는 문제입니다. 앞에서 몇번을 던져서 뭐가 나오든 신경을 쓸 필요없이 최근 3개의 눈을 기반으로 던질 수 있는 경우를 고려하면 쉽게 풀 수 있습니다. 만약 최근 3개가 5 3 4의 눈이 나왔다면, 현재 상금과 한번 더 던졌을때 다음에 올 눈 1~6에서의 기대값을 계속 구해가면서 더이상 던질 수 없을때 까지 반복하면 됩니다. #in.. 2020. 7. 23.
[BOJ] 백준 15892번: 사탕 줍는 로봇 https://www.acmicpc.net/problem/15892 15892번: 사탕 줍는 로봇 첫 번째 줄에 성원이네 집안에 있는 방의 개수를 나타내는 자연수 n(2 ≤ n ≤ 300)과 복도의 개수를 나타내는 자연수 m(1 ≤ m ≤ 5,000)이 공백으로 구분되어 주어진다. 두 번째 줄부터 m개의 줄에 �� www.acmicpc.net 사탕의 개수를 노드 간 연결된 간선의 용량으로 생각하면 네트워크 플로우 (최대 유량)으로 쉽게 풀 수 있음. 네트워크 플로우의 개념은 BFS로 시작->도착점 경로의 최소 유량 flow를 탐색하여 u->v 유량에 더해주고 역방향 v->u 유량에서 빼서 더이상 유량을 흘려보낼 수 없을 때 까지 반복합니다. 주의할 점은, 이 문제는 양방향이라 실수할 확률이 낮지만 단방향.. 2020. 7. 20.
[BOJ] 백준 2150번: Strongly Connected Component https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 강한 연결 요소 (SCC, Strongly Connected Component) 알고리즘은, v에서 u로가는 경로가 있을 때, 반대로 u에서 v로 갈 수 있는 경로가 존재하는 최대의 그룹 크기를 찾는 알고리즘입니다. 코사라주 알고리즘과 타잔 알고리즘으로 강한 연결 요소를 찾을 수 있는데, 본 포스팅에서는 코사라주 알고리즘에 대하.. 2020. 7. 17.

티스토리툴바