조합론5 [백준] 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. [프로그래머스] 주사위 고르기 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/258709 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이n개의 주사위를 2명이 나눠가진다. 주사위에 쓰인 수의 구성은 모두 다르다. 나눠 가진 주사위들의 합을 구해 점수가 큰 쪽이 승리하는데, A가 승리할 확률이 높도록 주사위를 나눠야 하는 문제이다. 먼저 주사위를 어떻게 나눌지 완탐했다. getDice()메소드를 만들어 비트마스킹을 이용해 어떤 주사위를 A가 선택할지 정해주었다. 선택이 완료되면 calculateWinRate()메소드를 통해 승률을.. 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. [백준] 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. 이전 1 다음