Algorithm221 [백준] 3078: 좋은 친구 - JAVA https://www.acmicpc.net/problem/3078 풀이학생의 이름이 등수 순으로 주어진다. 등수가 k를 넘지 않으면서 이름의 길이가 같으면 좋은 친구이다. 좋은 친구의 쌍을 구해야 한다. 처음에는 단순히 큐를 사용하면 되는 문제인 것 같았다. 하지만 메모리초과... 어떻게 푸는지 방법을 찾아보았다. 이름의 길이가 2~20이므로 길이 20의 큐 배열을 선언한다. 입력받은 문자열의 길이를 len이라고 한다면, 큐 배열의 len 인덱스에 들어있는 값이 해당 번호와 자신의 번호의 차가 k보다 크다면 poll 해준다. poll 해준 뒤 남아있는 개수를 정답에 더해준다. 그 후 같은 인덱스에 자신의 등수를 넣어주면 된다. 메모리: 47332KB시간: 368ms언어: Java 11import jav.. 2024. 5. 19. [백준] 14395: 4연산 - JAVA https://www.acmicpc.net/problem/14395 풀이정수 s를 t로 바꾸는 최소 연산 횟수를 구한다. 연산은 `+, -, *, /` 를 사용할 수 있다.' 가능한 방법이 여러가지면 사전순으로 하나를 출력해야 하기 때문에 아스키 코드 순서인 `*, +, -, /` 순으로 탐색하였다. s와 t가 10의 9제곱까지 주어지므로 최대 LIMIT을 1,000,000,000으로 잡았다. 탐색중에 이 범위를 넘지 않는 연산만 진행했다. `/` 연산의 경우 숫자가 0이 아닐때만 사용가능하므로 처리해주었다. bfs 탐색을 통해 가장 먼저 나오는 결과를 출력하면 끝. 메모리: 14424KB시간: 132ms언어: Java 11import java.io.*;import java.util.*;public c.. 2024. 5. 19. [백준] 19942: 다이어트 - JAVA https://www.acmicpc.net/problem/19942 풀이각 재료별로 단백질, 지방, 탄수화물, 비타민 함유량과 가격이 주어진다. 재료들을 혼합하여 영양분들을 더해 최소 영양분을 충족해야 한다.(최소 금액으로) 부분집합을 만들어 만들어진 집합에 대해 영양분들의 합이 만족하는지 판별해주었다. 비용이 이전의 비용보다 적은 경우에 갱신해주었고, 재료들의 번호를 출력해야 했기에 `TreeSet` 을 선언하여 담았다. 이전의 최소 비용과 같은 경우에는 TreeSet에 추가만 해주었고, 이전 최소 비용보다 작은 값이여서 갱신이 필요한 경우엔 TreeSet을 새로 선언하여 추가하였다. TreeSet은 사전 순으로 정렬되기 때문에 TreeSet의 `first()` 메소드를 이용해 답을 출력했다. 메모리.. 2024. 5. 19. [백준] 14267: 회사 문화 1 - JAVA https://www.acmicpc.net/problem/14267 풀이상사가 직속 부하를 칭찬할 수 있는데 a가 b에게 10의 칭찬을 했다면 b의 직속 부하인 c도 10의 칭찬을 받는 것이 된다. 각 번호의 직원마다 직속 상사의 번호가 주어져 저장했다. 직속 상사로부터 칭찬을 받은 직원의 번호와 칭찬 수치가 주어지는데, int배열을 만들어 저장했다. 1번이 사장이므로 1번부터 시작하여 트리를 타고 내려가면서 int배열의 값을 부모 노드에서 자식 노드에 더해주는 식으로 구현했다. 메모리: 76068KB시간: 792ms언어: Java 11import java.io.*;import java.util.*;public class Main { static ArrayList> list; static i.. 2024. 5. 19. [백준] 18427: 함께 블록 쌓기 - JAVA https://www.acmicpc.net/problem/18427 풀이N명의 학생이 들고있는 블럭을 인 당 최대 한 개 사용하여 높이 H를 정확하게 맞출 수 있는 경우의 수를 구해야한다. dp배열을 2차원으로 만들었다. `new int[n + 1][h + 1]` 1번 학생부터 시작하여 1~h까지 높이에 대해 경우의 수를 구한다. n번 학생이 특정 높이 h에 대해 만들 수 있는 경우의 수는 다음과 같이 구할 수 있다. `(n번 학생이 들고 있는 h 높이의 블록의 수) + (n-1번 학생까지 했을 때 h 높이를 만든 경우의 수) + (n번 학생이 가진 a 높이의 블록 + n-1번 학생까지 했을 때 h-a 높이를 만든 경우의 수)` 이 방법을 코드로 옮기면 다음과 같다.for (int i = 1; i = h.. 2024. 5. 19. [백준] 16987: 계란으로 계란치기 - JAVA https://www.acmicpc.net/problem/16987 풀이계란마다 내구도, 무게가 주어진다. 계란끼리 부딪혔을 때 내구도는 상대 계란의 무게만큼 깎이는데, 내구도가 0이하가 되면 계란이 깨진다. 계란을 최대 몇개 깰 수 있는지 구해야 한다. dfs를 통해 1번 계란 부터 진행했다. idx번 계란을 어떤 계란과 부딪혔을 때 계란들의 내구도와 깨진 개수를 갱신해 idx+1번으로 넘어가 진행한다. 반복문을 통해 해당 계란이 여러 번호의 계란과 부딪히는 것을 시뮬레이션해볼 수 있도록 부딪힌 후에 결과를 초기화 해주는 과정이 필요했다. 메모리: 15708KB시간: 232ms언어: Java 11import java.io.*;import java.util.*;public class Main { .. 2024. 5. 19. [백준] 29703: 펭귄의 하루 - JAVA https://www.acmicpc.net/problem/29703 풀이펭귄의 현재 위치 S에서 출발하여, 물고기 서식지 F 중 한 곳을 지나, 펭귄의 집 H로 가는 최단 시간을 구하는 문제이다. 두 번의 bfs를 통해 해결했다. S부터 시작하는 bfs를 통해 출발지부터 물고기 서식지들 까지의 시간을 저장했다. H부터 시작하는 bfs를 통해 H에서 F까지 얼마나 걸리는 지 저장했다. S -> F, F -> H 의 시간이 각각 저장된 배열들을 이용해 어떤 F를 지났을 때 두 값의 합이 최소가 되는지 구했다. 메모리: 124844KB시간: 708ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int[][] vect.. 2024. 5. 19. [백준] 16562: 친구비 - JAVA https://www.acmicpc.net/problem/16562 풀이k원의 예산으로 모든 사람과 친구가 되는 방법을 구해야 한다. 친구마다 각각 원하는 친구비가 주어지고, 해당 학생과 어떤 학생이 친구인지 주어진다. 다만, 친구의 친구는 친구이기 때문에 이를 이용해 최소한의 비용으로 친구가 되어야 한다. 따라서 주어진 친구들의 관계를 이용해 그룹을 지었다. 각 그룹에 한 번 씩만 친구비를 전달하면 모든 친구와 친구가 될 수 있다. union 메서드를 이용해 그룹을 지어주었다. 이떄 그룹의 대표 번호는 친구비가 가장 적은 사람으로 저장해주었다. 그룹을 모두 지은 뒤, 친구비를 더해 계산해주었다. 메모리: 18320KB시간: 220ms언어: Java 11import java.io.*;import jav.. 2024. 5. 19. [백준] 3109: 빵집 - JAVA https://www.acmicpc.net/problem/3109 풀이첫번째 열에서 마지막 열까지 파이프를 이어야한다. 이때 이동은 `{ -1, 1 }`, `{ 0, 1 }`, `{ 1, 1 }` 으로 할 수 있다. 탐색 방향 순서를 위에서부터 채우기 위해 -1, 0, 1 순으로 탐색한다. 배열에 방문했다는 체크를 하면서 탐색하며, 마지막까지 같다면 개수를 늘리고, `true`를 리턴한다. 실패할 경우 `false`를 리턴하여 종료한다. 방문 체크를 먼저 하고 탐색을 보냈기 때문에 실패한 칸은 다시 가보지 않아도 되게하여 시간초과를 해결할 수 있었다. 메모리: 34748KB시간: 400ms언어: Java 11import java.io.*;import java.util.*;public class Main.. 2024. 5. 19. [백준] 1477: 휴게소 세우기 - JAVA https://www.acmicpc.net/problem/1477 풀이이분탐색으로 풀어야겠다는 생각이 바로 들지 않았다. 우선순위큐를 이용해 풀어보려고했는데 잘 되지 않아서 구글링의 도움을 받았다. 이분탐색을 하는데 휴게소들 사이의 거리를 기준으로 탐색한다. 이분탐색을 어떤걸 기준으로 하는지 찾는 것이 어려웠다. 휴게소 간 거리이기때문에 left를 1로, right를 l-1로 놓고 진행했다. mid만큼의 거리를 두고 이미 있는 휴게소들 사이에 mid만큼 거리로 몇 개나 더 세울 수 있는지 체크한다. 이렇게 헤아린 개수를 통해 구간을 좁혀나간다. 메모리: 14268KB시간: 128ms언어: Java 11import java.io.*;import java.util.*;public class Main { .. 2024. 5. 19. 이전 1 2 3 4 5 6 7 8 ··· 23 다음