브루트포스 알고리즘34 [백준]3151: 합이 0 - JAVA https://www.acmicpc.net/problem/3151 풀이N개의 숫자들 중 3개를 선택하여 그들의 합을 0으로 만드는 경우의 수를 찾는 문제이다. 배열에 숫자들을 저장하여 정렬한다. 첫 번째 숫자를 선택하고, 그 다음 숫자를 left, 배열의 끝 숫자를 right로 놓고 left와 right를 조정하여 합이 0이 되는 수를 찾는다. 선택한 숫자를 node라고 할 때, `node + arr[left] + arr[right]` 가 0이 되는 경우를 찾아 정답을 증가시킨다. `arr[left]` 와 `arr[right]`가 같은 경우에는 left부터 right까지의 수가 n개라고 할 때 nC2의 조합을 구하는 것과 같다. 처음 선택한 수를 0부터 시작하여 증가시키면서 값이 0보다 커질 때까지 실행.. 2024. 9. 3. [백준] 10881: 프로도의 선물 포장 - JAVA https://www.acmicpc.net/problem/10881 풀이세 개의 선물을 한 상자에 넣어 포장해야 한다. 선물 세 개를 상자에 넣는 방법은 두 가지 경우로 생각해볼 수 있다. `ABC` 처럼 일렬로 놓는 방법과 A와 B를 위아래로 쌓고, C를 옆에 놓는 방법이 있다. 순열을 구해 3개의 선물의 순서를 구한다. 가로, 세로 길이가 주어진 선물을 그대로 놓을지 회전시켜 놓을지 `pos`배열에 저장하면서 순열을 구했다. 선물들의 순서와 회전여부가 주어지면 놓는 방법 2가지 경우에 필요한 상자의 크기를 구해 정답을 갱신했다. 메모리: 28108KB시간: 352ms언어: Java 11import java.io.*;import java.util.*;public class Main { stati.. 2024. 8. 13. [백준] 20208: 진우의 민트초코우유 - JAVA https://www.acmicpc.net/problem/20208 풀이집의 위치와 우유의 위치가 주어진다. 체력이 0이 되면 이동을 할 수 없다. 우유를 먹으면 일정 체력이 회복되는데 최대한 많은 우유를 먹고 집으로 돌아와야 한다. 처음에는 dfs로 풀이를 했는데 시간초과가 발생했다. 문제의 조건을 다시 보니 우유의 개수가 10개를 넘지 않는다는 것을 확인했다. 지도를 전부 저장하지 않고, 우유의 위치만 list로 저장해줬다. 해당 리스트를 탐색하며 우유에 방문처리하면서 진행한다. 함수가 실행될 때 현재 위치와 집의 위치의 거리를 계산하여 남아있는 체력으로 돌아올 수 있다면 답을 갱신해줬다. 메모리: 15160KB시간: 528ms언어: Java 11import java.io.*;import java... 2024. 7. 19. [백준] 21278: 호석이 두 마리 치킨 - JAVA https://www.acmicpc.net/problem/21278 풀이건물들이 도로로 연결되어있고, 2개의 건물을 골라 치킨집을 열어야 한다. 이때, 치킨집으로부터 각 건물들까지의 거리의 합이 최소가 되게 해야한다. 먼저 플로이드-워셜 알고리즘을 통해 각 건물들 사이의 거리를 구했다. for (int k = 1; k 건물들 사이의 거리를 구한 후, 2개의 건물을 정해 거리의 합을 계산해 정답을 갱신해주었다. 메모리: 17220KB시간: 192ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int n, m; static int[][] dist; public static void main(String[.. 2024. 7. 13. [백준] 1239: 차트 - JAVA https://www.acmicpc.net/problem/1239 풀이원형 차트를 만들 때, 각 구간의 비율이 주어진다. 각 구간을 적절히 배치했을 때 원의 중심을 지나는 선의 개수를 최대로 해야한다. 어떤 구간합이 50이 되면 원의 중심을 지나는 선이 생긴다. 순열을 만들어 각 구간들을 어떻게 배치할지 정했다. 이때, set을 이용해 중복제거를 해줬다. 구해진 순서를 슬라이딩윈도우 방식으로 구간합이 50이 되는 개수를 찾아 정답을 갱신해줬다. 메모리: 49480KB시간: 416ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int n, answer; static int[] arr, selected; .. 2024. 6. 27. [백준] 19942: 다이어트 - JAVA https://www.acmicpc.net/problem/19942 풀이각 재료별로 단백질, 지방, 탄수화물, 비타민 함유량과 가격이 주어진다. 재료들을 혼합하여 영양분들을 더해 최소 영양분을 충족해야 한다.(최소 금액으로) 부분집합을 만들어 만들어진 집합에 대해 영양분들의 합이 만족하는지 판별해주었다. 비용이 이전의 비용보다 적은 경우에 갱신해주었고, 재료들의 번호를 출력해야 했기에 `TreeSet` 을 선언하여 담았다. 이전의 최소 비용과 같은 경우에는 TreeSet에 추가만 해주었고, 이전 최소 비용보다 작은 값이여서 갱신이 필요한 경우엔 TreeSet을 새로 선언하여 추가하였다. TreeSet은 사전 순으로 정렬되기 때문에 TreeSet의 `first()` 메소드를 이용해 답을 출력했다. 메모리.. 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. [백준] 17471: 게리맨더링 - JAVA https://www.acmicpc.net/problem/17471 풀이구역들이 서로 어떻게 연결되어있는지 주어진다. 구역들을 2개의 그룹으로 나눠, 각각의 인구수의 합의 차가 최소가 되게 해야한다. 그룹들은 서로 연결되있어야한다. 먼저, n개의 지역을 2개의 그룹으로 나눴다. 나눠진 그룹안의 지역들이 서로 연결되어 있는지 체크 후, answer를 갱신해주었다. 메모리: 16012KB시간: 160ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int n, answer; static int[] population; static ArrayList> graph; static boolean[] sel;.. 2024. 5. 19. [백준] 1497: 기타콘서트 - JAVA https://www.acmicpc.net/problem/1497 풀이처음에는 기타마다 연주할 수 있는 곡을 비트마스킹으로 체크하려고 했으나 곡의 개수가 최대 50까지 되기 때문에 int범위에서 비트마스킹을 할 수 없었다. 따라서 boolean 이차원 배열을 만들어 체크했다. N개의 기타로 만들 수 있는 조합을 모두 만들어 연주할 수 있는 곡을 체크해줬다. 비트마스킹을 사용하려고 했던 것이 아쉬워 조합을 만들 때 비트마스킹을 이용했다.for (int i = 1; i 1부터 2의 N제곱까지의 자연수 중 비트의 자리수가 1인 것이 선택된 기타이다. 메모리: 14548KB시간: 136ms언어: Java 11import java.util.*;import java.io.*;public class Main { .. 2024. 5. 18. [백준] 1062: 가르침 - JAVA https://www.acmicpc.net/problem/1062 풀이배운 알파벳을 체크하기 위해 비트마스킹을 이용했다. 알파벳은 26자인데 int자료형은 2의 31제곱까지 표현이 가능하므로 비트마스킹을 적용할 수 있다. a, n, t, i, c 5개 문자를 -97 해서 숫자로 바꾼 뒤 체크해주었다. K개의 글자를 배울 수 있으므로 조합을 통해 K개를 채워주었다. K개가 되었다면 주어진 단어 중 읽을 수 있는 단어를 카운트해줬다. 메모리: 15216KB시간: 300ms언어: Java 11import java.util.*;import java.io.*;public class Main { static int N, K, ans; static String[] arr; public static .. 2024. 5. 18. 이전 1 2 3 4 다음