전체 글

백준 - Packet Routing 6951 java

https://www.acmicpc.net/problem/6951 6951번: Packet Routing The date is October 29th, 1969. Today, scientists at UCLA made history by exchanging data between two computers over a network. The transmission wasn't very spectacular: only the first two letters of the word login were received before the system crashed. www.acmicpc.net [문제 해설] 해당 문제는 패킷 라우팅에 관한 설명입니다. 패킷에서 패킷까지의 이동 거리가 주어지고 입력으로 들어오는 패..

백준 - 친구비 16562

https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net [문제 접근] union-find 알고리즘 사용 union 함수에서 부모 설정할 때 cost가 더 낮은 친구로 설정 1 ~ N 까지 find 함수로 부모를 찾아 준 후 cost를 더해 주고, 방문 처리를 통해 이미 더해준 집합은 건너뜀 [Java] import java.io.BufferedReader; import java.io...

백준 - 연속합 1912 java

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net [문제 접근] input으로 주어진 값이 너무 커서 완전 탐색으로 접근하게되면 시간 복잡도가 어마어마 해질거 같았습니다. 그래서 dp 메모제이션으로 문제 접근을 해봤습니다. 우선 저는 연속된 수를 골랐을 때, 연속된 수를 고르지 않았을 때 두 가지 경우로 나누어서 생각했는데요 dp[i] 배열에는 i번째 수에서 최대로 만들 수 있는 값을 저장하면 점화식은 아래와 같아집니다. dp[i] = Math.max(dp..

백준 - 문자열 집합 조합하기 25328

[문제 해결] 문자열 X, Y, Z 에서 K개를 선택해 나온 조합에서 같은 문자열이 2개 이상 나온 문자열을 출력하는 문제 X, Y, Z 조합을 구하면서 HashMap을 이용해 문자열이 나온 빈도수를 기록한다. 빈도수가 2 이상인 문자열들을 오름차순 출력 [Java] import java.io.*; import java.util.*; public class Main { static HashMap map = new HashMap(); public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String x = br.readLi..

백준 - 캠프 준비 16938

https://www.acmicpc.net/problem/16938 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 조합 백트래킹으로 완전 탐색 [Java] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int ans = 0; static int arr[]; static boolean visited[]; static int l,r,x; public static void main(String[] args) throws IOException { BufferedR..

[백준] - 도영이가 만든 맛있는 음식 2691

https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net N의 범위가 1 ~ 10 이여서 조합 완전 탐색으로 해결했습니다. [Java] import java.io.*; import java.util.*; public class Main { static long ans = Integer.MAX_VALUE; public static void main(String args[]) throws IOException { BufferedRead..