문제 풀이
-
[백준] 1949번 우수마을문제 풀이 2020. 8. 23. 17:34
1949 우수마을 풀이)백준 2533번 사회망서비스 문제랑 똑같이 dp를 사용해서 풀면 된다.사회망 문제 설명) https://comyoung.tistory.com/41 +)트리는 사이클이 없는 무방향 그래프이므로 어느 정점에서 시작하든 상관없다. 나같은 경우는 1번 마을을 트리의 root라고 생각하고 시작해줬다. 주의사항처음에 트리 구현할 때무조건 번호 작은 노드가 번호가 큰 노드의 부모이게 만들어, 양방향으로 마을을 연결되지 않게 했었다.이렇게 풀면 트리가 제대로 구현되지 않아 틀리게 된다.반례) 1-3, 2-3 코드) 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include us..
-
[백준] 4386번 별자리 만들기문제 풀이 2020. 8. 22. 17:44
4386 별자리 만들기 문제도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것다. 별자리의 조건은 다음과 같다-별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.-모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오. 입력첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다. 출력첫째 줄에 정답을 출력한다...
-
[백준] 1197번 최소 스패닝 트리문제 풀이 2020. 8. 22. 17:28
1197 최소 스패닝 트리 문제그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 ..
-
[백준] 1717번 집합의 표현문제 풀이 2020. 8. 21. 18:43
1717 집합의 표현 문제초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오. 입력첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a..
-
[백준] 2263번 트리의 순회문제 풀이 2020. 8. 20. 22:22
2263 트리의 순회 문제n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.입력첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.출력첫째 줄에 프리오더를 출력한다. 풀이)순회방법을 미리 알았어야 풀기 쉬운 문제이다. 다음과 같은 트리가 있을 시 1. inorder : 중위순회 - left→root→right순으로 읽는다. - 위의 그림을 읽는 순서 : 2→1→3 2. postorder : 후위순회 - left→right→root 순으로 읽는다. - 위의 그림을 읽는..
-
[백준] 13913번 숨바꼭질4문제 풀이 2020. 8. 19. 17:18
13913 숨바꼭질4 문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.둘째 줄에 어떻게 이동해야 하는지 공백으로 구..
-
[백준] 1167번 트리의 지름문제 풀이 2020. 8. 18. 21:24
1167 트리의 지름 문제트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. 입력트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 매겨져 있다고 생각한다)먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 ..
-
[백준] 12886번 돌 그룹문제 풀이 2020. 8. 17. 19:23
12886 돌그룹 문제오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다.크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오. 입력첫째 줄에 A, B, C가 주어진다. (1 ≤ A, B, C ≤ 500) 출력돌을 같은 개수로 만들 수..