good_da22

백준 7569번 토마토 (JAVA) 문제 난이도 골드 5 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 풀이 3차원 배열을 사용한 너비 우선 탐색 자바에서 3차원 배열 사용시 면, 행, 열 사용에 주의 너비 우선 탐색을 통해 현재 익은 토마토로 주변 토마토의 영향을 파악 익지 않은 토마토의 전체 개수를 초기에 구한 후 탐색이 돌때마다 이를 최신화한다. 코드 public class Main { static int M, N, H, need, answer; static int[][][] box; static Queue que = new ArrayDeque(); static int[] dDep = {-1, 1}; static int[] dRow = {-1, 1, 0, 0}; static int[] dC..

백준 14889번 스타트와 링크(JAVA) 문제 난이도 실버 2 알고리즘 분류 브루트포스 알고리즘 백트래킹 풀이 N명 중 N/2 명을 선택하여 능력치 합을 구하고 선택되지 않은 N/2명 의 능력치 합을 구한다. N 명 중 N/2 명을 뽑는 조합 6명 중 1, 2, 3을 뽑는 것은 4, 5, 6을 뽑는 것과 같다. N/2를 뽑는 조합을 절반만 수행할 수 있다. 1 ~ N 까지의 수 중 N / 2개를 선택하는 과정에서 1을 포함하는 경우와 1을 포함하지 않는 경우로 나눌 수 있다. 1을 포함하는 N / 2개를 선택하고 선택되지 않는 경우와 비교 코드 public class Main { static int N; static int[][] arr; static int answer; static int[] num..

백준 21578번 꿀 따기 (JAVA) 문제 난이도 골드 5 알고리즘 분류 그리디 알고리즘 누적 합 많은 조건 분기 풀이 누적 합을 이용하기 위해 입력 시 누적된 합을 계산한다. 이후 중간에 벌통이 위치한 경우에서 사용하기 위해 입력 값 중 최댓값을 찾는다. (양쪽 끝 위치 제외) 벌통의 위치 왼쪽 끝에 있는 경우 오른쪽 끝에 있는 경우 중간에 있는 경우 왼쪽 끝에 있는 경우 한 마리 벌은 오른쪽 끝에 위치 (누적 합을 최대로 만들기 위해) 나머지 한 마리는 오른쪽 벌과 왼쪽 끝에 위치한 벌통 사이에 위치 오른쪽 끝에 위치한 벌이 따는 꿀의 합 = (N - 2 ~ 0 까지의 합 - 나머지 벌의 위치에 있는 꿀의 값) 중간에 위치한 벌이 따는 꿀의 합 = (현재위치 - 1 ~ 0 까지의합) 오른쪽 끝에 있..

백준 13975번 파일 합치기3 (JAVA) 문제 난이도 골드 4 알고리즘 분류 자료구조 그리디 알고리즘 우선순위 큐 풀이 모든 파일이 합쳐지는 동안 최초 두 파일을 합치는 경우의 비용은 누적된다. 누적되는 비용의 최소화 필요 가장 작은 비용의 두 파일을 합치고 하나의 파일로 연산한다. 코드 public class Main { public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); Strin..

백준 17204번 죽음의 게임 (JAVA) 문제 난이도 실버 3 알고리즘 분류 구현 그래프 이론 그래프 탐색 시뮬레이션 풀이 출발번호(0) 부터 목표번호(K)로 가는 최솟값 구하기 어떤 방법으로도 K로 갈 수 없는 경우는 K에 도착하기 전에 사이클이 발생한다. 코드 public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); StringBuilder sb =..

백준 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..

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 =..