목록백준 (183)
Study hard
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 � www.acmicpc.net [풀이] 이분탐색으로 풀 수 있었다. 먼저 입력으로 받은 집의 좌표들을 정렬하고, low는 1, high는 가장 처음 집과 가장 마지막 집의 거리로 설정하였다. #include #include using namespace std; #define Max 200001 int N, C; int Home[Max]; bool Share(int dist..
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, www.acmicpc.net [풀이] 이분 탐색으로 해결하였다. 모든 변수를 long long으로 선언해야 범위에 벗어나지 않았다. #include #include //max using namespace std; #define Max 1000001 long long N, M; long long Tree[Max]; bool cutTree(int height) { long long trees = 0; for (int i = 0; ..
https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net [풀이] 이분탐색으로 푸는 문제였다. 처음에 재귀로 풀려고 했지만 시간초과에 계속 틀렸다고 떠서 반복문으로 바꿨다. 초기 low는 어찌 됐든 1이상의 길이로 자를 수 있으니까 1, high는 입력되는 전선들 중 가장 긴 전선의 길이로 설정했다. 그리고 이분탐색으로 low부터 high까지 길이중 K개 전선들을 N개 이상으로 나눌 수 있는 가장 긴 길이를 구했다. #inc..
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 �� www.acmicpc.net [풀이] 각 노드를 시작점으로 하여 bfs를 돌려보고 각 노드에서 가장 먼 노드까지의 길이중 가장 긴 것을 출력한다. #include #include #include #include //max #include //memset using namespace std; struct Pos { int x, cnt; }; struct Weight { int x, weight;//이어진 노..
https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] dfs로 부모 노드를 찾는 문제였다. 입력에서 부모자식 관계를 알 수 없기 때문에 양방향으로 저장해주었다. 1부터 차례로 자식노드를 찾으면서 자식노드의 부모노드가 현재노드임을 저장해주었다. #include #include using namespace std; #define Max 100001 int N; int Parent[Max]; bool check[Max]; vectorTree[Max]; void input() { cin >> N; for (in..
https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net [풀이] Tree[][2]배열에 각 노드의 왼쪽 자식 노드 번호와 오른쪽 자식 노드 번호를 저장하였다. #include using namespace std; int N; char Tree[27][2];//[x][0]:x의 왼쪽 자식, [x][1]:x의 오른쪽 자식 void input() { cin >> N; for (int i = 0; i < N; i++) { char a, b, c; cin..