Programming/Algorithm
-
[Java] 백준 2875 대회 or 인턴Programming/Algorithm 2021. 3. 10. 20:48
문제 대회에 나갈 수 있는 1 팀은 여자2 남자1로 구성되어 있다. 여자는 총 m명 남자는 총 n명이 있다고 할 때 m+n명중 k명은 반드시 인턴에 참여해야한다. 인턴에 참여한 인원은 대회에 참가할 수 없다고 할 때, 만들 수 있는 최대 팀수를 구하는 문제이다. 풀이 - 먼저 만들 수 있는 팀 수의 최댓값(teams)을 구한다. - 만들 수 있는 팀의 개수는 '총 여자 수/2(1팀에 최소로 들어가야하는 여자 수)'와 총 남자 수/1(1팀에 최소로 들어가야 하는 남자 수)' 중 더 작은 값이다. - int teams = Math.min(M/2, N/1) - 총 인원에서 팀에 속한 사람들 (teams * 3)을 뺀 나머지 인원을 구한다. - 이 인원이 K보다 크거나 같아야 K명 이상이 인턴에 참여가능한 것이..
-
[Java] 백준 11047 동전 0Programming/Algorithm 2021. 3. 10. 20:42
문제 n 종류의 동전이 주어진다. 동전을 적절히 사용해서 가치의 합을 K로 만드는 문제이다. 풀이 K보다 작은 동전의 가치중 가장 큰 값으로 K를 나눠 동전의 개수를 구하고 나머지로 K를 초기화한다. K가 0이 되면 사용한 동전의 총 개수를 출력한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Inpu..
-
[Java] 백준 2579 계단 오르기Programming/Algorithm 2021. 3. 10. 20:38
문제 계단을 밟으면 해당 계단에 쓰인 점수를 얻을 수 있다고 할 때, 얻을 수 있는 점수의 최댓값을 구하는 문제이다. 규칙 - 한 번에 1계단 or 2계단 - 연속 3계단 불가능 - 시작점은 계단 아님 - 도착점은 반드시 밟기 풀이 현재 위치가 n번째 계단이라고 할 때, n번째 계단에서 얻을 수 있는 점수의 최댓값을 생각해보자. 연속 3칸을 밟은 것은 불가능하기 때문에 고려해야할 경우는 2가지이다. 1) n-2번째 계단을 밟은 뒤 n번째 계단을 밟은 경우 - dp[n-2] + scores[n] 2) n-3번째 계단을 밟은 뒤 n-1번째 계단을 밟고 n번째 계단을 밟은 경우 - dp[n-3] + scores[n-1] + scores[n] 즉, 다음의 두 가지 경우 중 큰 값으로 dp[n]을 초기화 시키면 ..
-
[Java] 백준 2447 별찍기 10Programming/Algorithm 2021. 3. 9. 00:48
문제 크기 3의 패턴이 주어지고, 크기가 3이상일 때 가운데는 공백 나머지는 n/3 패턴으로 둘러싼 형태의 모양을 출력하는 문제이다. 풀이 공백이 되어야 하는 부분과 아닌 부분으로 분할해서 재귀하는 것이 풀이의 핵심이다. - n을 3으로 나누어 현재 영역을 9등분한다. - 이 때 가운데는 공백이라는 조건이 있으므로, 5번째 영역은 항상 공백이 되어야 한다. - n이 1이라면 별을 출력하고, 아니라면 나누어진 영역을 재탐색한다. 코드 import java.io.*; public class Main { static char[][] map; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRea..
-
[Java] 백준 1992 쿼드트리Programming/Algorithm 2021. 3. 9. 00:36
문제 주어진 영역 내의 숫자가 모두 같은 숫자면 해당 숫자를 출력하고, 아니라면 영역을 4등분하여 숫자가 같은지 다시 검사를 하는 문제이다. 풀이 1. 현재 영역의 숫자를 검사 2. 모두 일치하지 않는다면 현재 변의 길이(n)을 1/2하고, 현재 좌표를 기준으로 4영역으로 분할하여 함수를 재호출 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int[][] map; static StringBuilder sb; public static void main(String[] args) throws IOException { BufferedRea..
-
[Java] 백준 11729 하노이 탑 이동 순서Programming/Algorithm 2021. 3. 5. 19:59
문제 하노이의 탑에 있는 N개의 원판을 '1'에서 '3'으로 이동시킬 때, 탑의 이동 순서를 출력하는 문제이다. 하노이의 탑 풀이는 공식처럼 외워서 사용하는 편이 편한 것 같다. 핵심적인 논리는 N개의 원판을 '1'에서 '3'으로 이동시키기 위해 우선 N-1개를 '1'에서 '2'(도움닫이 공간)으로 이동시킨 후, 마지막 1개의 원판을 '3'으로 이동시키는 것이다. 이동시킨 후엔 '2'(도움닫이 공간)으로 이동시킨 원판을 다시 '3'으로 이동하는 방식으로 진행한다. 그림을 그려가며 이해하는 것이 좋다. 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main {..
-
[Java] 백준 1780 종이의 개수Programming/Algorithm 2021. 3. 5. 19:53
문제 잘라진 종이가 한 숫자로만 이루어져 있는지를 검사하고 그렇다면 종이 개수를 추가하고, 아니라면 9등분으로 나눠 다시 종이 내의 숫자를 검사하는 문제이다. 9등분으로 나누는 부분을 재귀로 처리하였다. 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N; static int[][] map; static int[] res; public static void main(String[] args) throws IOException { solution(); } static v..