기록방

👉 문제링크 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 🔸 문제 분석 🔸 N개의 도시가 있고, M개의 버스가 있다. M개의 버스는 한 도시에서 다른 도시까지 드는 버스 비용이 있다. 출발 도시부터 도착지 도시까지 버스 비용의 최소 값을 출력한다. 전형적인 다익스트라 알고리즘 문제이다. 그래프에서 한 정점에서 특정 정점까지의 최소비용을 구해야 한다. M개의 버스는 단방향 연결을 나타낸다. 목적지가 나올 때 까지, 각 정점의 최단 거리를 갱신해간다. 목적지에 방문하면 그때의..

👉 문제링크 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 🔸 문제 분석 🔸 0부터 n까지 원소가 1개씩 들어있는 n+1개의 집합에서 입력 연산의 결과를 출력한다. 0은 두 집합의 합집합 연산을 수행한다. 1은 두 집합이 같은 집합인지 확인해, 같으면 "YES" 혹은 "yes", 다르면 "NO" 혹은 "no"를 출력한다. 전형적인 union-find 알고리즘 문제이다. 합집합 연산은 union을 사용한다. 두 집합이 같은 집합인지 확인은 find를 사용해 반환값을 비교한..

👉 문제링크 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 🔸 문제 분석 🔸 n * m 도화지에서 연결된 1의 개수의 최대값을 출력한다. BFS혹은 DFS로 연결된 1을 탐색한다. 연결된 1 무리의 개수와 그 중 최대값을 출력한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import..

👉 문제링크 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 🔸 문제 분석 🔸 R x C 크기의 2차원 배열의 0번 열부터 C-1번 열까지 파이프를 연결하고자 한다. '.' 에는 파이프를 놓을 수 있고, 'x'에는 놓을 수 없다. 첫 열과 끝 열은 '.' 로만 채워져있다. 파이프는 오른쪽 위, 오른쪽, 오른쪽 아래로만 연결할 수 있다. 놓을 수 있는 파이프의 최대값을 출력한다. 🔸 풀이 전략 🔸 R이 최대 1만, C가 최대 500이므로 효율적인 선택 방법이 필요하다.(그리디) 최대한 많은 파이프를 두기 위해서는 가능한 위쪽으..

👉 문제링크 6987번: 월드컵 월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부 www.acmicpc.net 🔸 문제 분석 🔸 월드컵에서 6개의 국가가 서로 1번씩 경기를 뛰고 나온 결과로 가능한지 불가능한지 판단한다. 4번의 경기 결과가 주어지는데, 한 나라의 승, 무, 패의 수로 입력된다. 가능한 결과이면 1, 불가능한 결과이면 0을 반환한다. 6개의 국가에서 경기를 뛰는 경우의 수는 6C2 = 6*5/2 = 15개 이다. 승/무/패 상관없이 총 15번의 경기가 가능하면, 올바른 경기 결과이다. 입력 제한이 0~6 이므로, 한 국가의 승무패의 합이 5가 되..