N개의 장미를 가장 싸게 구매할 수 있는 금액을 구하는 문제입니다. 가성비가 좋은 장미와 가성비가 좋지 못한 장미로 나눕니다. 이를 X와 Y로 볼 경우 Y는 X개 보다 적은 경우에만 정답이 나올 수 있습니다. 그래서 Y를 0개부터 X-1개 까지 구매하는 경우의 수를 전부 확인하여 결과값을 찾아냈습니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter..
그리디, 이분탐색으로 문제를 해결할 수 있습니다. 각 마을 중에 한곳에 우체국을 세울 때 각 사람들과 우체국의 거리의 합을 가장 적게 할 수 있는 위치를 찾아야 합니다. 1. 마을 인덱스를 기준으로 정렬합니다. 2. 누적합을 통해서 마을 사람들 수를 구해줍니다. 3. 이분탐색을 통해서 해당하는 위치까지의 사람들 수와 이후의 사람들 수를 비교합니다. 4-1. 해당 위치까지의 사람들 수가 더 많을 때 현재위치를 right로 변경하고 3번을 진행합니다. 4-2. 해당 위치까지의 사람들 수가 더 적을 때 현재위치를 left로 변경하고 3번을 진행합니다. 위의 과정을 통해서 최적의 위치를 찾고 출력해줍니다. import java.io.*; import java.util.*; public class Main { p..
다이나믹 프로그래밍 문제입니다. WHEE가 나올 수 있는 경우의 수를 모두 찾고 1000000007로 나눈 나머지를 출력해야 합니다. 크기가 3인 배열을 선언합니다. => long[] arr = new long[3]; 1. W일 경우 0번 인덱스에 +1 2. H일 경우 1번 인덱스에 0번 인덱스에 있는 값만큼 추가해줍니다. 3. E일 경우 - 2번 인덱스에 있는 값만큼 결과값에 더해줍니다. - 2번 인덱스에 있는 값만큼 2번인덱스에 더해줍니다. - 2번 인덱스에 1번 인덱스에 있는 값만큼 추가해줍니다. 위를 반복하여 최종적으로 WHEE가 가능한 경우를 찾을 수 있습니다. import java.util.*; import java.io.*; public class Main { public static voi..
이분탐색 문제입니다. 잡을 수 있는 동물의 수를 구하는 문제입니다. 총을 쏠 수 있는 사로와 동물의 위치, 현재 총의 사거리가 주어집니다. 아래의 식으로 해당 사로에서 해당하는 동물을 잡을 수 있는지 구했습니다. |사로x - 동물x| + 동물y > 총의 사정거리 가능한 경우 결과를 +1 불가능한 경우 현재 사로x가 동물x보다 작은 경우 - left = mid + 1 현재 사로x가 동물x보다 큰 경우 - right = mid - 1 이분탐색으로 left가 right보다 클 때까지 반복합니다. 모든 동물에 반복하여 카운트 된 수를 출력해줍니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] a..
토마토와 딸기를 심을 때 겹쳐서 심게된 곳의 개수와 위치를 출력하는 문제입니다. 2명의 사람이 연속해서 K개를 심었는데 어떤부분이 겹쳐져있는지 찾아야합니다. 입력을 받고 배열에 저장할 때 1의 개수를 세어 주었습니다. K * 2 - (1의 개수)를 해주면 겹쳐서 심어져있는 수를 알 수 있습니다. 총 3가지 경우로 구분하였습니다. (cnt = 겹쳐진 개수) 1. cnt == K 2. cnt == 1 3. cnt > 1 1번의 경우 겹쳐진 수와 K가 같다는건 두 사람 모두 같은곳에 심었다는 것을 의미합니다. 반복문을 통해서 1이 있는 곳들의 위치를 모두 출력해 주었습니다. 2번의 경우 토마토와 딸기가 크로스 모양(세로, 가로)로 하나가 겹쳐있는 상태와 ( TTOSS ) 토마토와 딸기가 직선으로 하나만 겹쳐 ..
브루트포스, 수학 문제입니다. 조건에 맞는 수가 몇개있는지 찾아야합니다. 1. K가지의 숫자로 이루어진 수 => (K가 3인 경우, 100~999까지의 수 중에서 숫자가 겹치지 않는 수들 (101, 110, 373, 888 등 제외) 2. 서로 다른 두 개의 소수의 합으로 나타낼 수 있는 경우 3. 1번의 수들 중 M으로 나누어 떨어지지 않을 때 까지 나눈 수가 소수의 곱인 경우 => 나누어 떨어지지 않을 때 : M이 5인 경우, (9 => 9), (10 => 2), (24 => 24), (25 => 1), (30 => 6) 코드 진행 순서 1. 소수를 찾기. 2. 소수의 합으로 만들 수 있는 값들 찾기 3. 소수의 곱으로 만들 수 있는 값들 찾기 4. M으로 나누어 떨어진 수가 3번에 해당하는지 찾기 ..
SCV의 체력을 전부 0으로 만드는데 최소한의 공격 횟수를 구하는 문제입니다. 최대 3개의 SCV가 있으므로 가능한 경우는 다음과 같습니다. 1. [1, 3, 9] 2. [1, 9, 3] 3. [3, 1, 9] 4. [3, 9, 1] 5. [9, 1, 3] 6. [9, 3, 1] 위의 경우 모두 탐색해주었습니다. 0, 0, 0에서 한번의 공격으로 가능한 경우 입니다. 1, 3, 9 1, 9, 3 3, 1, 9 3, 9, 1 9, 1, 3 9, 3, 1 위의 값들을 정렬하면 전부 1, 3, 9가 됩니다. SCV를 정렬해서 1, 3, 9가 되는지 확인하면 되므로 6가지의 경우의 수에 대해서 정렬을 해주어서 같은 경우는 visit배열을 통해서 방문처리를 하여 중복 방문을 없애주었습니다. import java...
시뮬레이션 문제입니다. 4개 이상의 인접한 색이 있을 경우 해당 색 블럭들은 터지게됩니다. 모든 위치에 동시에 터지게 되고 이를 1번의 연쇄로 처리합니다. 처리가 된 후 중력이 적용되어 공중에 있는 블럭들은 아래로 내려갑니다. 터질 수 있는 경우가 없을 때 까지 반복하여 몇번의 연쇄가 발생하는지 출력해줍니다. import java.util.*; import java.io.*; public class Main { static BufferedReader br; static BufferedWriter bw; static StringTokenizer st; static int n; static int m; static int cnt; static int result; static int bombCnt; stat..