good_da22

백준 2922번 크면서 작은 수 (JAVA) 문제 난이도 실버 3 알고리즘 분류 문자열 브루트포스 알고리즘 백트래킹 풀이 주어진 수를 모두 이용하여 새로운 수를 만들기(자리 수를 유지해야한다.) 주어진 수를 모두 이용하기 때문에 순열을 생성한다. 주어진 수보다 크지만 그 중 가장 작은 수를 탐색해야하기 때문에 정렬 후 순열을 생성하여 작은 값부터 탐색한다. 코드 public class Main { private static char[] split; private static int value; private static int N; private static int[] numbers; private static boolean[] visited; private static int answer; public..

1722번 순열의 순서 (JAVA) 문제 난이도 골드 5 알고리즘 분류 구현 수학 조합론 풀이 최대 20! 연산이 발생할 수 있기 때문에 직접 순열을 구하는 경우 시간 복잡도가 매우 증가한다. 20!을 담기 위해서 타입 선언에 유의한다. 1 ~ N 이 담긴 리스트 생성 소문제 1인 경우, 주어진 K번 째 순열 구하기 계산을 위해 K - 1 (0번째 순열부터) 순열의 개수는 N! 개 앞에 위치할 수를 선택하고 그 뒤에 (N-1)! 만큼의 순열이 올 수 있다. 따라서 K / (N-1)! 을 통해서 앞에 올 숫자가 몇 번째인지를 구할 수 있다. 해당 위치에 올 숫자가 남은 숫자 중 몇 번째 숫자인지 구하고 리스트를 통해서 해당 숫자를 가져온다. 가져온 숫자를 리스트에서 삭제해 중복을 방지한다. 해당 자리에 올..

19939번 박 터뜨리기 문제 난이도 실버 5 알고리즘 분류 그리디 알고리즘 풀이 각 바구니에는 1개 이상의 공이 존재해야한다. 각 바구니에 들어있는 공의 개수는 모두 달라야 한다. 바구니에 담긴 공의 최대 개수와 최소 개수의 차이를 최소로 하기 위해선 1개 씩 증가하면서 담기 1개씩 증가하면서 담을 수 없는 경우, 공의 개수를 달리하면서 모든 바구니를 채울 수 없다. 1개씩 증가하면서 담을 수 있는 경우, 공을 다 담은 경우 종료 공이 바구니의 개수보다 많이 남은 경우, 각 바구니에 1개 씩 추가 공이 바구니의 개수보다 적게 남은 경우, 공이 많이 담긴 바구니부터 1개씩 추가해야 겹치지 않는다. 코드 public class Main { public static void main(String[] args..

1251번 단어 나누기 문제 난이도 실버 5 알고리즘 분류 구현 문자열 브루트포스 알고리즘 정렬 풀이 조합을 통해 나눌 구역을 선택한다. 3구역으로 나눌 때 각 구역은 최소 한 글자를 포함해야하기 0 ~ len - 1 까지의 수 중 2개의 수를 선택한다. 선택된 수로 나뉜 구역에 문자열을 뒤집고 새로운 문자열을 생성 문자열을 리스트에 담고 리스트를 정렬, 가장 첫 번째 문자열을 출력한다. 코드 public class Main { private static int len; private static char[] word; private static int[] number; private static List list; public static void main(String[] args) throws Exc..

1326번 폴짝폴짝 (Java) 문제 난이도 Silver 2 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 풀이 현재 위치에서 갈 수 있는 징검다리 선택 다음 징검다리 방문 여부 확인 방문이 안된 경우 방문 체크, 몇 번째 방문인지 기록 현재 위치 기준 배수만큼 이동 가능(좌우로 이동 가능) 코드 // 백준, 1326번, 폴짝폴짝, 실버2 // https://www.acmicpc.net/problem/1326 public class Main { private static int N; private static int start; private static int end; private static int[] arr; private static int answer; public static voi..

1931번 회의실 배정 문제 난이도 Silver 1 알고리즘 분류 그리디 알고리즘 정렬 풀이 회의실 배정 문제는 가장 빨리 끝나는 회의를 우선적으로 배정해야한다. 2차원 배열에서 원하는 기준으로 정렬을 하기 위해 compare 메서드 사용 코드 public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st = new StringTo..

2615번 오목 문제 난이도 Silver2 알고리즘 분류 구현 브루트포스 알고리즘 풀이 public class Main { static int[] dx = { -1, 1, 0, 0, -1, 1, -1, 1 }; // |,-, \, / static int[] dy = { 0, 0, -1, 1, -1, 1, 1, -1 }; static int[][] map = new int[19][19]; static boolean check(int color, int x, int y) { return x > 18 || x 18 || y < 0 || map[x][y] != color; } static int[] count(int color, int x, int y, int idx) { int ansX =..

2438번 별 찍기 -1 문제 난이도 Bronze5 알고리즘 분류 그리디 알고리즘 풀이 public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(br.readLine()); for (int i = 1; i

5855번 거스름돈 문제 난이도 Bronze2 알고리즘 분류 그리디 알고리즘 풀이 public class Main { static final int Money = 1000; static int[] change = { 500, 100, 50, 10, 5, 1 }; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int input = Integer.parseInt(br.readLine())..