본문 바로가기

Algorithm221

[백준] 15686: 치킨 배달 - JAVA https://www.acmicpc.net/problem/15686 풀이브루트포스, 백트래킹문제. 치킨집 중 M개를 골라 집들과의 거리를 구한 합의 최솟값을 구하는 문제. 치킨집과 집을 리스트에 넣고 치킨집중 M개의 조합을 만들었다. 만들어진 치킨집의 조합을 이용해 집과 치킨집 거리의 최솟값들의 합을 구해주었다.  메모리: 15112KB시간: 220ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Node { int r; int c; public Node(int r, int c) { this.r = r; this.c = c; .. 2024. 5. 11.
[백준] 10819: 차이를 최대로 - JAVA https://www.acmicpc.net/problem/10819 풀이브루트포스, 백트래킹문제. N정수가 주어지고 순서를 적절히 바꿔 다음 식의 최댓값을 구하는 문제였다. `|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|` 배열을 저장하고 0 ~ N-1 까지의 인덱스를 순열로 만들어 계산 후 최댓값을 구해줬다. 비트마스크를 이용해 방문처리했다.  메모리: 14944KB시간: 148ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int N, ans; static int[] arr, selected; public static void main(Strin.. 2024. 5. 11.
[백준] 3980: 선발 명단 - JAVA https://www.acmicpc.net/problem/3980 풀이브루트포스, 백트래킹문제였다. 선수들의 능력치가 주어지고, 11개의 포지션에 배치하여 최댓값을 얻어야 한다. 능력치가 0인 포지션에는 들어갈 수 없다. 1번 선수부터 포지션을 선택하면서 dfs탐색을 했다. 11번 선수까지 포지션 배정을 마치고 최대값을 정해주면 끝. 해당 포지션에 선수가 배치되었는지 방문처리를 하는 부분이 필요했는데, 비트마스크를 이용해 boolean배열을 만드는 것보다 조금 속도가 빨랐다.  메모리: 15640KB시간: 160ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int[][] arr; static int ans.. 2024. 5. 11.
[백준] 11582: 치킨 TOP N - JAVA https://www.acmicpc.net/problem/11582 풀이구간을 나눠 정렬해주면 되는 간단한 문제였다. N/k 길이 씩 구간을 정해 그 구간을 정렬하여 출력한다. 임시로 배열이나 리스트를 만들고 구간의 값을 넣은 뒤 정렬해주었다. 임시로 저장할 공간을 만들 때 세가지 경우를 실험해 보았다. 1. 배열을 매번 새로 선언. 2. 리스트를 전역으로 선언하고 매번 list를 clear. 3. 리스트를 매번 새로 선언. 배열을 매번 선언하는 것이 메모리, 시간이 모두 적게 나왔다. 리스트의 clear를 이용하는 것보다 매번 선언하는 것이 시간이 적게 걸렸다. 리스트의 clear함수는 리스트를 돌면서 null로 채우는 방식인데 list의 사이즈가 클 때는 clear보다 새로 선언하는 것이 더 빠르다... 2024. 5. 11.
[백준] 1756: 피자 굽기 - JAVA https://www.acmicpc.net/problem/1756 풀이구현 + 그리디 문제. 피자 반죽을 오븐의 사이즈에 맞춰서 넣는데 위에서부터 내려가다가 오븐의 사이즈가 피자 사이즈보다 작으면 그 위칸에 위치한다. 예제에서 오븐의 사이즈가 { 5, 6, 4, 3, 6, 2, 3 } 으로 주어졌는데 두번째 칸에는 위에서부터 내려와야 하므로 최대 5 사이즈의 피자가 들어갈 수 있다. 따라서 오븐의 사이즈 배열을 { 5, 5, 4, 3, 3, 2, 2 } 와 같이 바꿔주었다. 단순하게 아래에서부터 탐색하여 위치를 찾는 방법과 이분탐색으로 위치를 찾는 방법이 있었다.  단순 탐색메모리: 64440KB시간: 532ms언어: Java 11import java.io.*;import java.util.*;publi.. 2024. 5. 11.
[백준] 28071: 승형이의 사탕 사기 - JAVA https://www.acmicpc.net/problem/28071 풀이dp문제이다. M개의 사탕 상자를 가져갈 수 있고, 사탕 개수의 총 합은 K로 나누어 떨어져야 한다. 상자의 개수와 나머지에 따라 dp배열을 생성한다. dp[i][j]에서 i를 상자의 개수, j를 나머지라고 하면 dp[i][j]의 값은 i-1개의 상자에서 "j - 현재 사탕상자의 사탕 개수"일때의 dp값을 이용하여 갱신한다. "j - 현재 사탕상자의 사탕 개수"가 음수가 되면 안되기 때문에 Math.floorMod연산을 사용했다. dp배열을 채운 후 나머지가 0인 경우 중 최댓값을 구한다.  메모리: 15152KB시간: 424ms언어: Java 11import java.io.*;import java.util.*;public class.. 2024. 5. 11.
[백준] 1174: 줄어드는 수 - JAVA https://www.acmicpc.net/problem/1174 풀이321, 950처럼 왼쪽부터 자리수가 감소할 때 줄어드는 수를 찾는 문제. 줄어드는 수를 저장해놓고 N번째 줄어드는 수를 출력해주었다. 줄어드는 수 중 가장 큰수는 "9876543210"이다. (long 범위) {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}의 배열을 만들어 놓고 앞에서부터 해당 인덱스를 선택할지 여부를 조합으로 수를 만든다. 만든 수를 list에 넣어 정렬했다. list를 인덱스로 접근하여 출력하면 문제 끝. 조합을 할 때, 재귀로 접근할 수도 있고, 비트마스킹을 이용할 수 있다. 처음에 재귀로 문제를 풀고, 비트로 하는 방법을 찾아봤다.  재귀메모리: 14500KB시간: 152ms언어: Java 11impor.. 2024. 5. 11.
[백준] 21738: 얼음깨기 펭귄 - JAVA https://www.acmicpc.net/problem/21738 풀이그래프 탐색 문제. 펭귄이 얼음 위에 올라가있는데 떨어지지 않으려면 연결된 지지대 얼음 2개가 필요하다. 최소한의 얼음만 남기고 얼음을 깨야한다. 펭귄의 위치로부터 탐색한다. 먼저 발견한 얼음이 가깝다는 것이므로 먼저 발견한 2개의 지지대 얼음을 제외한 나머지 얼음은 깨는 것으로 한다.  메모리: 152136KB시간: 696ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int N, S, P, ans; static ArrayList> list; public static void main(String[] args) throws IOE.. 2024. 5. 11.
[백준] 19699: 소-난다! - JAVA https://www.acmicpc.net/problem/19699 풀이소 M마리의 합이 소수인지 판별하는 문제였다. N마리의 소가 있다. N마리 중 M마리의 조합을 만들어 소수인지 판별해주었다. 소수는 에라토스테네스의 체를 구현하여 미리 배열에 정보를 담아놓았다. 오름차순으로 출력과 중복 제거를 위해 TreeSet을 이용했고, Set출력을 위해 Stream을 이용했다.  메모리: 14296KB시간: 128ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int N, M; static int[] cow, group; static boolean[] prime; static TreeSet ans; .. 2024. 5. 11.
[백준] 3359: 사각 사각 - JAVA https://www.acmicpc.net/problem/3359 풀이DP문제이다. 사각형을 각각 가로로 놓을지 세로로 놓을지 정해서 위쪽 둘레의 최댓값을 찾는다. dp배열을 이차원배열로 만들어 현재 사각형을 가로로 놓는다면 [0]에, 세로로 놓는다면 [1]에 값을 넣는다. 옆면까지 생각해야한다. 이전 dp배열에서 선택안한 변과 현재 선택안한 변의 차이를 더해 최댓값을 현재 dp배열에 더해준다.  메모리: 14480KB시간: 140ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader b.. 2024. 5. 11.

티스토리툴바