algorithm/boj7 백준 1967 트리의 지름 1. 문제 링크 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 2. 풀이 위 사진처럼 자식 노드부터 순차적으로 탐색해 나가면서 부모 노드로 올라갈 때에는 최댓값 2개를 골라 더해준 후 정답 값보다 크면 정답 값을 업데이트해 준다. 그러고 나서 리턴 값으로는 자식에서 올라온 값 중 가장 큰 값을 리턴해 준다. #include #include #include using namespace std; class Element { p.. 2021. 10. 5. 백준 2407 조합 1. 문제 링크 https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 2. 풀이 파스칼의 삼각형에서 제시하는 점화식을 활용해 DP방식으로 풀 수 있다. 문제는 long long 타입조차 감당 안될 정도로 숫자가 커진다는 것. 따라서 숫자 표현을 string으로 해야 한다. #include #include #include using namespace std; int n, m; string arr[101][101]; string StringPlus(const string& s1, const string& s2) { string result = ""; int tmp; a.. 2021. 10. 3. 백준 11779 최소비용 구하기 2 1. 문제 링크 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 2. 풀이 전형적인 최단거리 문제이다. 다만 최소비용을 갖는 경로를 출력하는 부분이 추가되었다. 이 부분은 각 정점마다 최소 비용이 결정되는 시점에, 해당 정점으로 오기 바로 직전 정점을 별도의 배열에 표시해 둠으로 서 해결했다. //n(1≤n≤1,000)개의 도시 => 정점 //m(1≤m≤100,000)개의 버스 => 간선 #include #inc.. 2021. 10. 3. 백준 13549 숨바꼭질 3 1. 문제 링크 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 2. 풀이 지금 위치에서 갈 수 있는 경우의 수와 비용은 아래와 같다. 이동: (지금 위치) * 2 비용: 0 이동: (지금 위치) - 1 비용: 1 이동: (지금 위치) +1 비용: 1 위 조건에서, N -> K로 이동하는 최단거리를 구하면 되는 문제이다. #include #include using namespace std; class Eleme.. 2021. 10. 3. 이전 1 2 다음
