브루트포스91 백준 3011 자바 - 이름 지어주기 (BOJ 3011 JAVA) 문제 : boj3011 1. A에서 B 구간의 최대가 10^9이므로, 우선 모든 경우를 봐서는 통과할 수 없음을 알 수 있다. 그럼 뭔가 정답 구간을 정할 수 있는 방법이 있다는 얘기이다. 이 문제의 경우, 어떠한 X 지점에 대해 모든 N지점 중 거리의 차가 최소인 지점을 최대한 멀리 두려고 한다(min{|X-Pi|, i ∈ [1,N]}). 즉, X는 모든 N개의 지점 P_i와 최대한 멀리 떨어지면 된다. 2. 입력이 4 10 46 56 70 10 70 인 경우를 생각해보자. 어떻게 해야 N개의 지점에서 가장 멀리 떨어진 X 지점을 모두 보지 않고 찾을 수 있을까? 최선의 선택은 각 지점들의 중간지점들을 보면, 그 중 가장 양쪽의 차이가 큰 지점을 고르면 될 것임을 생각해볼 수 있다(그리디). 그리고 하.. 2021. 12. 17. 백준 14911 자바 - 궁합 쌍 찾기 (BOJ 14911 JAVA) 문제 : boj14911 1. 주어지는 수의 개수가 주어지지 않으므로 입력받기 전에 총 배열의 크기를 알 수 없다. 미리 최대 개수 배열을 만들어 입력받은 후 처리하거나, 자바의 split 합수를 사용해 처리하면 된다. 2. 최대 개수가 10개밖에 안되므로 모든 경우의 수를 보면 된다. 다만 주의점은 사전 순으로 출력해야 한다는 부분인데, 이를 위해 정렬 후 모든 경우를 보면 된다. 또한 문제에 명시적으로 나타나진 않았으나, '사전 순으로 앞서는 기준은 a < c이거나, a == c 이면서, b < d 인 것' 에 따라 a==c이면서 b==d인 경우는 정의되지 않은 것을 알 수 있다. 따라서 서로 다른 쌍이라 할지라도, 동일한 출력값은 출력하면 안된다. 예를들어 입력이 1 1 1 1 1 2 와 같을 경우.. 2021. 12. 15. 백준 9327 자바 - 용량 확보 (BOJ 9327 JAVA) 문제 : boj9327 음주코딩이 더 코딩이 잘된다는게 사실인것같다. 평소엔 시간 꽤나 걸리던 골1과 플5 문제가 둘다 한방에 해결됬다. 뭐지.. 이상하다. 아무래도 이것저것 복잡도 계산 해볼 정신머리가 없어서 무지성으로 짜보다 보니 오히려 빨리 해결하는 것 같다 ㅋㅋㅋ 결국 입력으로 주어진 n개의 용량x2에 대해 존재 가능한 모든 합의 경우의 수 중, 확보하려는 용량 e보다 같거나 큰 것 중 가장 가까운걸 출력하면 된다. 예를들어 n개가 400 600 700 일 경우 존재 가능한 모든 합의 경우의 수는 다음과 같다. 400 1000 1100 600 1300 700 이걸 정렬하면 400 600 700 1000 1100 1300 이 되고, 이 중 만약 e가 1050이라면 1050보다 같거나 큰 수중 가장 .. 2021. 12. 13. 백준 14382 자바 - 숫자세는 양 (Large) (BOJ 14382 JAVA) 문제 : boj14382 INSOMNIA인 경우부터 생각해보자. 일단 각 자리 중 1~9중 어느 수라도 들어가면 배수에서 모든 수가 나타날 수 있다. 따라서 INSOMNIA인 경우는 n이 0인 경우 하나 뿐이다. 그 외의 경우는 실제로 n, 2n, 3n, ...을 해보면서 각 자리수에 포함된 숫자들을 찾아내어 모든 수를 찾았는지 확인하면 된다. 모든 수를 찾는 것은 미리 0~9까지를 넣은 해시를 준비해두고 찾을 때 마다 remove 후 size를 확인해봐도 될테고, 내 경우엔 remain=10 과 boolean 배열을 두고 새로운 수를 찾으면 remain을 감소시켜서 remain이 0이 되면 모두 찾은것으로 판단했다. 코드 : github import java.io.DataInputStream; impo.. 2021. 12. 10. 백준 12001 자바 - Load Balancing (Bronze) (BOJ 12001 JAVA) 문제 : boj12001 일단 B를 기준으로 모두 살펴보게 되면 O(1,000,000^2)이 되므로 시간초과가 나게 된다. N이 100개밖에 안되므로, N을 기준으로 살펴보면 된다. 처음엔 N개를 입력받고 fence가 교차하는 지점을 모든 N개 지점의 (x+1, y+1)에 있다고 보고 그로 인해 나눠지는 4사분면을 카운팅하면 될꺼라고 생각했다. 예를들어 cow가 주황색 지점에 있는 다음과 같은 상태를 생각해보자. 그럼 다음과 같이 모든 지점의 (x+1, y+1) 지점을 기준으로 나눠보면 답을 찾을 수 있을꺼라 생각했다. 하지만 제출해보니 틀렸고, 반례를 찾아보니 다음과 같은 경우 불가하다. 위의 경우 다음과 같이 나누어야 한다. 어찌되었든 기존 아이디어인 각 지점의 (x+1, y+1)은 분명 맞는 아이디.. 2021. 12. 2. LeetCode 5 - Longest Palindromic Substring - Medium (Java) LeetCode도 자주 들어봤는데 한번도 해본적은 없어서 한번 풀어봤다. 일단 시간 제한이 안써있으면서 TLE(시간초과)는 뜨는게 상당히 거슬린다. 시간제한 알려주든가! 프로그래머스도 그게 좀 불만인경우가 많은데.. 그리고 남의 코드를 못본다는 점이 상당히 아쉬워서 메인 OJ(Online Judge)로는 별론 것 같다. 그래도 유명한 사이트니 간간히 생각날 때 하나씩 풀어보게 될 것 같다. 처음 해보는 사이트라 여기저기 눌러보다보니 DP 태그가 붙어있는걸 봤다. 이미 태그를 봐버린 이상 태그대로 푸는건 자존심 상하기도 하고 어차피 Brute Force(이하 BF)로도 가능할 것 같아서 BF(하지만 Back Tracking을 좀 끼얹은)로 풀어봤다. 1. 단순히 모든 경우를 보도록 짜게되면 다음과 같이 짜.. 2021. 11. 30. 백준 1515 자바 - 수 이어 쓰기 (BOJ 1515 JAVA) 문제 : boj 1515 입력으로 주어지는 수는 최대 3000자리이고, 0~9까지는 10개이다. 그러므로 대충 생각해봐도 아무리 최악의 케이스라 할지라도 3000 * 10 = 30000 이내에서 모두 찾아질 것임을 알 수 있다. 그러므로 brute force로 입력받은 값을 첫 자리부터 확인하며 1부터 30000까지 입력으로 받은 값에 대입해보며 하나씩 찾아나가면 된다. 예를들어 290119을 보자. 첫 자리수부터 확인한다. 여기서 base라는걸 1로 두고, base를 1씩 증가시키며 쭉 매칭시키자. 우선 'base=1'은 현재 pointer가 보고있는 2와 겹치는게 없으니 다음으로 넘어간다. 'base=2'는 pointer와 동일하므로 찾은거다. pointer를 전진한다. 그리고 base가 현재 1자리.. 2021. 11. 28. CodeForces 1569A - Balanced Substring (Java) 문제 : https://codeforces.com/contest/1569/problem/A 1. 입력을 받은 값에 대해 a와 b가 나온 횟수를 prefix sum으로 계산해둔다. -> 범위 내의 a와 b의 개수를 빠르게 구하기 위해 2. 그 후 모든 substring에 대해 누적합 배열에서 범위합이 동일한 경우가 있는지 확인한다. 코드 : github import java.io.DataInputStream; import java.io.IOException; public class Main { public static void main(String[] args) throws Exception { initFI(); int tc = nextInt(); StringBuilder sb = new StringBui.. 2021. 11. 27. 백준 5966 자바 - Cow Cotillion (BOJ 5966 JAVA) 문제 : https://www.acmicpc.net/problem/5966 '>'와 ''를 넣고, ''와 ''와 '') cnt1++; else cnt2++; if (cnt2>cnt1) return false; } if (cnt1!=cnt2) return false; return true; } private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); while (n-->0) { StringTokenizer st =.. 2021. 11. 23. 백준 21187 자바 - Pulling Their Weight (BOJ 21187 JAVA) 문제 : https://www.acmicpc.net/problem/21187 뭔가 복잡해보이는데, 좀 정리해보면 그냥 brute force로 해결 가능한 문제이다. 1 최대 10^5개의 동물의 무게가 주어진다. 그리고 각 무게는 2만 이하이므로, 전부 더해도 20억 이하로 Integer로 표현 가능한 수치이다. 2 사실 동물이 몇마리가 주어지든 상관없고 중요한 데이터는 결국 '1~20,000 사이의 각 무게를 가진 동물이 각 몇마리씩 존재하는지' 이다. 3 정렬이 필요할것같이 생겼지만, 사실 무게가 2만 이하라서 배열에 카운팅한다면 정렬은 따로 필요 없다. 다음의 입력을 보자. 6 5 7 5 5 3 4 위 입력을 배열로 카운팅해보면 다음과 같다. 4 그럼 이제 index 기준으로 1부터 20000까지를 .. 2021. 11. 22. 이전 1 ··· 6 7 8 9 10 다음
