기록방

👉 문제링크 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 🔸 문제 분석 🔸 N개의 자연수 중 M개를 고른 수열을 모두 구한다. 수열은 중복되선 안되며 사전 순으로 증가하는 순서로 출력한다. N개의 자연수는 중복이 있을 수 있다. 순열로 M개의 원소를 고르고, 중복을 제거하면 된다. 🔸 코드 🔸 import java.io.*; import java.util.ArrayList; import java.util.Collections; import java.util.StringTokenizer; public cla..

👉 문제링크 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 🔸 문제 분석 🔸 문제 내용 N명의 사람과 M개의 파티가 있다. 진실을 아는 사람이 참여한 파티에서는 진실만 말해야 한다. 진실을 말한 파티에 있던 사람들도 진실을 아는 사람이 된다. 거짓을 말할 수 있는 파티의 수를 출력한다. 풀이 전략 같은 파티 참가자를 연결해야 한다. 각 파티별 참가자 List와 개인 별 참가 파티 List를 만든다. BFS로 진실을 말한 파티와 진실을 알게된 사람들을 추가해 나간다. 진실을 말하지 않은 파티의 수를 출력한다. 2024...

👉 문제링크 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 🔸 문제 분석 🔸 N개의 집에 R,G,B 3가지 색이 연속하지 않도록 칠한다. 각 집의 세 가지 색에 대한 비용이 주어진다. 모든 집을 칠하는 최소비용을 출력한다. 칠하는 경우의 수를 구하면 3x2x2x...x2 = 3x2x(n-1) = 6(n-1) n은 최대 1,000이므로, 칠하는 경우의 수는 최대 5994가지 가지수가 많지 않아 재귀, 백트래킹을 사용한 브루트 포스도 가능할 것 같지만, 시간은 0.5초이므로 DB를 이용한다..

👉 문제링크 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 🔸 문제 분석 🔸 N명의 학생들을 키 순서대로 줄을 세운다. 모두의 키 정보가 주어지는 것이 아니라, 두 학생을 비교해서 누가 앞에 오는지에 대한 정보만 주어진다. 위상 정렬 알고리즘에 대한 간단한 문제이다. 키가 큰 학생이 앞에 오는지, 작은 학생이 앞에 오는지에 대한 정보는 없고, 누가 앞으로 오느냐만 주어진다. 따라서 답이 여러가지가 될 수 있으므로 서브테스크 문제이다. BFS로 간단히 풀이할 수 있다..

👉 문제링크 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 🔸 문제 분석 🔸 N개의 수직선 위 집들의 좌표가 입력으로 주어진다. C개의 공유기를 설치하려는데, 가장 가까운 공유기의 거리를 최대로 하고자 한다. 공유기의 거리를 이분탐색과 같은 형태인 매개변수 탐색으로 찾아낸다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; im..