본문 바로가기

brute force11

[백준] 17779번: 게리맨더링 2 (Java) 1. 문제설명재현시는 NxN 크기의 격자로 나타낸다. 각 칸은 구역(r, c)을 의미한다. 구역을 다섯 개의 선거구로 나눠야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다.시간 제한: 1초메모리 제한: 512MB 2. 접근 방식가능한 모든 (x, y, d1, d2) 조합을 탐색하여 각 구역을 나누기 위한 조건을 만족하는지 확인한다.경계선에 따라 5개의 구역을 나눈다. 경계선(5구역)을 먼저 설정한 뒤, 각 구역(1~4구역)의 인구를 계산한다.각 구역별 인구 차이를 계산한 뒤, 그 차이의 최소값을 갱신한다. 3. 최종 코드import java.io.*;import java.util.*;public class Main { static int n; static boolean[].. 2024. 9. 20.
[백준] 14888번: 연산자 끼워넣기 (Java) 1. 문제설명N개의 수로 이루어진 수열에서, 수와 수 사이에 연산자를 하나씩 넣어 수식을 만들 수 있다. 식의 계산은 연산자 우선순위를 무시하고 앞에서부터 진행한다. 나눗셈의 경우 몫만 취하며, 음수를 나눌 때는 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼다.N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구한다. (주어진 수의 순서를 바꿀 수 없고, 어떤 식이더라도 -10억보다 크거나 같고, 10억보다 작거나 같은 INT 범위의 결과가 나오는 입력만 주어진다.)시간 제한: 2초메모리 제한: 512MB 2. 접근 방식수와 연산자를 배열에 저장한다.모든 경우의 식을 계산해야 한다. ⇒ 완전탐색, 백트래킹메서드에서 “다음 계산할 수의 인덱스(`numI.. 2024. 9. 13.
[백준] 16987번: 계란으로 계란치기 (Java) 1. 문제설명계란은 내구도와 무게에 대한 정보가 주어지고, 왼쪽부터 차례로 들어 한 번씩만 다른 계란 쳐 최대한 많은 계란을 깨는 문제이다. 계란의 내구도는 상대 계란으 무게만큼 깎이게 되고, 내구도가 0 이하가 되면 깨진다.계란을 치는 과정:가장 왼쪽 계란을 든다.들고 있는 계란으로 다른 계란 중 하나를 친다. 만약 손에 든 계란이 깨졌거나 다른 모든 계란이 깨진 경우 넘어간다.최근에 든 계란의 오른쪽 계란을 들고 2번 과정을 반복한다. 가장 오른쪽 계란을 들게 되면 종료한다.시간 제한: 2초메모리 제한: 512MB 2. 접근 방식참고: https://buly.kr/4bgWSet계란의 내구도와 무게를 각각 다른 배열에 저장한다.백트래킹을 사용하여 계란을 깨뜨리는 모든 경우의 수를 구한다.마지막 계란을 .. 2024. 9. 13.
[백준] 9095번: 1,2,3 더하기 (Java) 1. 문제설명정수 n이 주어졌을 때, n을 1, 2, 3의 조합으로 나타내는 방법의 수를 구하는 문제이다.시간 제한: 1초메모리 제한: 512MB 2. 접근 방식DP 방법을 사용한다.dp[i] 는 i를 1, 2, 3의 합으로 나타낼 수 있는 경우의 수를 저장한다.dp[i] 는 dp[i-1], dp[i-2],dp[i-3] 의 합으로 계산한다. 3. 올바른 접근 방식 및 해결 방식https://lotuslee.tistory.com/43 4. 최종 코드import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(.. 2024. 8. 26.
[백준] 22864번: 피로도 (Java) 1. 문제설명하루 한 시간 일하면 피로도가 A만큼 쌓이고 일은 B만큼 할 수 있다.만약 한 시간을 쉰다면 피로도는 C만큼 줄어든다. 피로도가 음수가 되면 0으로 바뀐다.피로도를 M이 넘지 않고 하루에 최대 일할 수 있는 시간을 구하는 문제이다.(하루는 24시간, 맨 처음 피로도는 0)시간 제한: 1초메모리 제한: 1024MB 2. 접근 방식=> 완전탐색 방법으로 1부터 24(하루)까지 일한 경우와 하지 않은 경우의 피로도를 계산한다.for문으로 1부터 24까지(하루)한 시간 일했을 때의 피로도를 계산하여 (next)next가 최대 피로도 M보다 작거나 같으면 결과값에 B를 더하고, 피로도를 A만큼 증가시킨다.next가 최대 피로도 M보다 크면 피로도를 C만큼 감소시킨다.만약 C만큼 감소시킨 피로도가 음수.. 2024. 8. 8.
[백준] 18511번: 큰 수 구성하기 (Java) 1. 문제설명N보다 작거나 같은 자연수 중에서, 집합 K의 원소로만 구성된 가장 큰 수를 출력하는 문제이다.ex) N=657이고, K={1, 5, 7}일 때 답은 577시간 제한: 1초메모리 제한: 256MB 2. 접근 방식=> 재귀함수를 이용해 모든 가능한 숫자를 조합하여, (완전탐색) N보다 작거나 같은 가장 큰 수를 찾는다.K의 원소를 배열에 저장하고, 오름차순 정렬한다.재귀를 사용해서 주어진 원소를 조합해 가능한 모든 수를 만든다.만들어진 수가 n보다 크면 종료한다.만들어진 수가 n보다 작거나 같은 경우 중 최대값을 찾는다.배열을 역순으로 탐색한다. (큰 수부터 만들기 위해) 3. 최종 코드import java.io.*;import java.util.*;public class Main { s.. 2024. 8. 8.
[백준] 19532번: 수학은 비대면강의입니다 (Java) 1. 문제설명$$ ax + by = c \\ dx + ey = f $$위 연립방정식에 대한 정수 $a, b, c, d, e, f$가 주어졌을 때, $(-999 ≤ a, b, c, d, e, f ≤ 999)$ 문제의 답인 $x$와 $y$를 구하는 문제이다.시간 제한: 1초메모리 제한: 1024MB 2. 접근 방식=> 완전탐색을 사용하여 x와 y에 -999부터 999까지 대입하여 해를 구한다.2중 for문을 이용해 x와 y에 -999부터 999까지의 수를 대입한다.두 개의 연립방정식에 맞으면 x와 y를 출력하고 프로그램 종료한다. 3. 최종 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] .. 2024. 8. 7.
반응형