우's 공부 일지

문제 문제 링크 : https://www.acmicpc.net/problem/1764 듣도 보도 못한 사람의 명단 구하기 조건 1 ≤ N ≤ 500,000 1 ≤ M ≤ 500,000 듣도 못한 사람들 중에 중복된 사람 X 보도 못한 사람들 중에 중복된 사람 X 입력 첫번째 줄 N M : N - 듣도 못한 사람 수, M - 보도 못한 사람 수 2 ~ (N+1)번째 줄 듣도 못한 사람들의 이름 (N+2) ~ (N+M+2)번째 줄 보도 못한 사람들의 이름 출력 듣도 보도 못한 사람의 수와 이름을 알파벳 순으로 출력하기 코드 로직 1) Map 이용해서 풀기 package backjoon; import java.util.*; // 듣보잡 public class No1764 { public static void ..

문제 링크 : https://www.acmicpc.net/problem/3020 장애물 최소 개수와 구간 개수 조건 2 ≤ N ≤ 200,000 2 ≤ H ≤ 500,000 N은 항상 짝수 N, H, 종유석 또는 석순의 길이 모두 양수 입력 첫번째 줄 N H : N - 동굴의 길이, H - 동굴의 높이 두번째 줄 ~ N+1 종유석 또는 석순의 길이( 1 ≤ 길이 < H) 출력 장애물 최소 개수와 구간 개수 로직 1) N x H를 하면 O(N^2)이므로 시간초과 발생 O(N) 구현 → 누적합 이용 package backjoon; import java.util.Arrays; import java.util.Scanner; public class No3020 { public static void main(Str..

문제 링크 : https://www.acmicpc.net/problem/1823 최대 수확량 구하기 조건 벼의 이익 : (벼의 가치) x (수확순서) 밭의 양쪽에 있는 벼만 수확 가능 입력 첫번째 줄 N : 1xN 벼 농장의 크기 (1 ≤ N ≤ 3,000) 두번째 줄 ~ (N+1) v(i) : 벼의 가치 (1 ≤ v(i) ≤ 1,000) 출력 벼수확의 최대 이익 로직 1) DFS DP 투포인터 package backjoon; import java.util.Scanner; public class No1823 { static int[] values; static int[][] dp; public static void main(String[] args) { Scanner sc = new Scanner(Sys..

문제 링크 : https://www.acmicpc.net/problem/2473 세 용액의 조합 중 가장 0에 가까운 용액의 특성값(오름차순) 입력 첫번째 줄 N : 용액의 수 (3 ≤ N ≤ 5,000) 두번째 줄 N개의 용액의 특성값들 (-1,000,000,000 ≤ 특성값 ≤ 1,000,000,000) 출력 세 용액의 조합 중 가장 0에 가까운 용액의 특성값(오름차순) 로직 1) 투포인터 package backjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.List; import java.util...

문제 링크 : https://www.acmicpc.net/problem/13164 티셔츠를 만드는 최소 비용 조건 티셔츠의 비용 계산 방법 한 조의 제일 작은 아이의 키와 제일 큰 아이의 키의 차이 한 조에는 최소 1명의 인원이 필요 입력 첫번째 줄 N K : 원생 수(1 ≤ N ≤ 300,000), 조의 개수(1 ≤ K ≤ N) 두번째 줄 원생의 키 : 오름차순(≤ 1,000,000,000) 출력 티셔츠를 만드는 최소 비용 로직 1) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void ..

문제 링크 : https://www.acmicpc.net/problem/1092 모든 박스를 배로 옮기는데 드는 시간의 최솟값 구하기 조건 1분에 1개의 박스를 옮길 수 있음 무게제한보다 무거운 박스는 크레인으로 옮길 수 없음 입력 첫번째 줄 N : 크레인 개수(1 ≤ N ≤ 50) 두번째 줄 각 크레인의 무게 제한( 1 ≤ {무게 제한} ≤ 1,000,000) 세번째 줄 M : 박스의 개수(1 ≤ M ≤ 10,000) 네번째 줄 각 박스의 무게(1 ≤ {무게} ≤ 1,000,000) 출력 모든 박스를 배로 옮기는데 드는 시간의 최솟값 모든 박스를 옮길 수 없는 경우에는 -1 출력 로직 1) 인터넷에서 풀이 참고 import java.io.*; import java.util.*; import java.u..

문제 링크 : https://www.acmicpc.net/problem/22945 팀 빌딩에서 나올 수 있는 팀 중 능력치의 최대값 구하기 입력 첫번째 줄 N : 개발자의 수 두번째 줄 xi : N의 개발자의 각 능력치가 공백으로 구분 출력 팀의 능력치 최댓값 로직 1) 투포인터 package backjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class No22945 { public static void main(String[] args) throws IOException { BufferedReader br = ne..

문제 링크 : https://www.acmicpc.net/problem/21758 획득 가능한 최대 꿀의 양 입력 첫번째 줄 N : 장소의 개수(3 ≤ N ≤ 100,000) 두번째 줄 꿀의 양이 공백으로 출력 출력 획득 가능한 최대 꿀의 양 로직 1) package backjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class No21758 { public static int[] honeys; // 꿀의 양 public static int max = 0; ..

문제 링크 : https://www.acmicpc.net/problem/1167 트리의 지름 출력하기 조건 트리의 지름 : 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것 입력 첫번째 줄 V : 트리의 정점의 개수(2 ≤ V ≤ 100,000) 두번째 줄 ~ (V+1)번째 줄 간선의 정보 : 정점 번호, 연결된 간선의 정보 한 쌍(정점번호, 두 정점 사이의 거리) 반복, 종료(-1) 출력 트리의 지름 구하기 로직 1) package backjoon; import java.io.*; import java.util.*; public class No1167 { public static void main(String[] args) throws IOException { BufferedReader br = ne..

문제 링크 : https://www.acmicpc.net/problem/22861 폴더의 파일을 정리 후 쿼리문을 통해서 파일 정보 확인 조건 같은 폴더 존재 X 같은 폴더 내에서 같은 파일명 존재 X 같은 이름의 파일은 서로 같은 내용을 가지고 있음 모든 폴더는 하나 이상의 파일을 가지고 있음 입력 첫번째 줄 N : main 폴더 안에 있는 폴더의 총 개수 (1 ≤ N ≤1,000) M : 파일의 총 개수 (1 ≤ M ≤ 1,000) 두번째 줄 ~ (N+M+1)번째 줄 P : 상위 폴더의 이름 (1 ≤ |P| ≤ 10) F : 폴더 또는 파일의 이름 (1 ≤ |F| ≤ 10) C : 폴더 = 1, 파일 = 0 (N+M+2)번째 줄 K : 옮기는 횟수 (0 ≤ K ≤ 1,000) (N+M+3)번째 줄 ~..