수학11 [백준] 1117: 색칠 1 - JAVA https://www.acmicpc.net/problem/1117 풀이W x H 크기의 종이를 가로로 f지점에서 접어 왼쪽이 오른쪽 위로 올라오게 접는다. 그 후 세로로 (c + 1) 등분한다. (x1, y1), (x2, y2)의 지점에 색칠을 하는데, 이 때 겹쳐있는 부분 모두 색칠된다. 색칠이 안된 부분의 크기를 구해야 한다. 처음에는 W x H크기의 배열을 만들어 접는 식으로 구현했다. 이 방법으로 정답은 나왔지만 제출하니 메모리 초과가 발생했다. 그래서 배열을 만들지 않고 바로 뺄 수 있지 않을까 생각했다. 먼저 가로로 접히는 부분을 구해줘야 한다. f가 W / 2보다 크다면 왼쪽 부분이 더 길어져 색칠할 때 오류가 생긴다. 따라서, f가 W/2보다 클 때는 접히는 부분을 W - f로 설정해주었다.. 2024. 6. 25. [백준] 13206: Professor KCM - JAVA https://www.acmicpc.net/problem/13206 풀이주어진 수들의 최대 공약수를 구해야 한다. 소인수 분해를 통해 각 소수의 최대 개수를 구하고, 이를 계산했다. for (int j = 2; j * j 위의 방식으로 소인수 분해를 했다. 해당하는 소수의 개수를 map배열에 카운트해주었다. 메모리: 314872KB시간: 2580ms언어: Java 11import java.io.*;import java.util.*;public class Main { static final long MOD = 1_000_000_007L; public static void main(String[] args) throws IOException { BufferedReader br = n.. 2024. 6. 10. [백준] 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. [백준] 2225: 합분해 - JAVA https://www.acmicpc.net/problem/2225 풀이0부터 N까지의 정수 K개를 더해서 합이 N이 되는 경우의 수를 구해야 한다. K개를 더해서 N이 되는 경우는 "K-1개를 더해서 N이 되는 경우에 0을 더한 경우", "K-1개를 더해서 N-1이 되는 경우에 1을 더한 경우", "K-1개를 더해서 N-2이 되는 경우에 2를 더한 경우", ... "K-1개를 더해서 0이 되는 경우에 N을 더한 경우" 들의 합으로 나타낼 수 있다. dp[k][n]에서 정수 1개를 이용해 n을 만드는 경우는 1개, 정수 k개를 이용해 0을 만드는 경우는 1개로 초기화 해주었다. 그 후 위의 경우들을 다 더하면서 저장하여 dp[k][n]을 출력하면 된다. 아래 코드에서 3중 for문에 있던for (int l.. 2024. 5. 17. [백준] 15824: 너 봄에는 캡사이신이 맛있단다 - JAVA https://www.acmicpc.net/problem/15824 풀이매운 정도를 배열로 입력받아 몇 개를 선택하여 조합을 만들 경우 그 안에서 최댓값과 최솟값의 차이가 그 조합의 맛의 정도가 된다. 이런 맛의 정도들의 합을 구하는 문제이다. 먼저 입력받은 배열을 정렬했다. i번째 인덱스의 경우 이 값이 최솟값이 되는 경우는 2^i개의 경우, 이 값이 최댓값이 되는 경우는 2^(N - i - 1)개의 경우가 된다. 2의 거듭제곱을 구하기 위해 분할정복을 이용했다. 메모리: 58472KB시간: 792ms언어: Java 11import java.util.*;import java.io.*;public class Main { static final int MOD = 1_000_000_007; st.. 2024. 5. 16. [백준] 9081: 단어 맞추기 - JAVA https://www.acmicpc.net/problem/9081 풀이C++에 있는 next permutation 함수를 구현하는 문제이다. 어떤 문자가 주어지면 그 문자의 알파벳들로 만들 수 있는 문자들 중 처음 주어진 문자의 다음에 올 문자를 찾는 문제였다. 조합으로 모든 경우를 만들어 set에 넣는 방식으로 구현하였는데 메모리초과로 실패했다. next permutaion이란 방법을 찾아 구현해보았다.1. 뒤에서부터 탐색하여 증가하지 않는 첫번째 인덱스를 찾는다.2. 다시 뒤에서부터 탐색하여 찾은 인덱스의 값보다 처음으로 큰 값이 나오는 인덱스를 찾는다.3. 두 인덱스의 값을 바꾸고 인덱스 뒤 부분을 정렬하여 붙인다.따라서, 주어진 단어를 int배열로 만들어 구현했다. 뒤에서부터 탐색해 값이 감소하는.. 2024. 5. 14. [백준] 9527: 1의 개수 세기 - JAVA https://www.acmicpc.net/problem/9527 풀이자연수 A부터 B까지 모든 수에 대해 이진수로 표현했을 때 1의 개수를 구해야한다. 자연수의 범위는 10의 16제곱까지였다. 2의 54제곱이 10의 16제곱을 넘어서 이진수로 54자리수까지 담는 배열을 만들었다.dp[i] = (dp[i - 1] 배열의 점화식은 위와 같다. i자리수는 i-1자리수의 모든 경우의 앞에 1을 붙이면 되기 때문이다. B까지의 개수에서 A-1까지의 개수를 빼주면 정답이다. 하지만 예를 들어 자연수 14가 주어지면 3자리까지의 개수를 더하고 나머지를 더 구해줘야 한다. 이진수들을 써본 결과 규칙을 찾았고 다음과 같은 식으로 계산할 수 있었다.return dp[digit - 1] + diff + count(n - .. 2024. 5. 12. [백준] 12850: 본대 산책2 - JAVA https://www.acmicpc.net/problem/12850 풀이결론부터 말하면 분할정복을 통해 행렬의 거듭제곱을 하는 문제였다. 각각의 포인트에서 연결된 길을 이차원배열에 저장했다. 초기 배열을 V1이라고 하면 V1[a][b]는 a에서 b로 1분만에 갈 수 있는 경로의 수를 의미한다. V1을 제곱한 것을 V2라고 하면 V2[a][b]는 a에서 b로 2분만에 갈 수 있는 경우의 수이다. 즉, Vx[a][b]는 a에서 b로 x분만에 갈 수 있는 경우의 수를 의미한다. 따라서 주어진 D만큼 V행렬을 제곱하여 V[0][0]을 구하면 D분만에 0에서 0으로 갈 수 있는 경우의 수이다. 분할정복은 doPow함수로 구현했고, 행렬의 곱셈은 multiply함수로 구현했다. 메모리: 14256KB시간: 124.. 2024. 5. 12. [백준] 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. 이전 1 2 다음