본문 바로가기

brute Force92

백준 1035 자바 - 조각 움직이기 (BOJ 1035 JAVA) 문제 : boj1035 처음엔 그리디로 풀어보려 했지만, 별다른 규칙을 찾지 못했다. 와중에 생각해보니 어차피 5x5 밖에 안되고, 조각은 최대 5개 이므로 최악의 경우라도 O(25^5*25*5) 정도로 풀 수 있다. 25^5는 5x5 크기의 보드에 5개의 조각을 모든 위치에 놓는 경우의 수이고, 해당 경우의 수에 대해 *25는 그 중 하나의 조각을 찾는 것이고, *5는 5개가 인접해있는지 확인하는 것이다. 저대로는 당연히 불가능하지만, 여기에 백트래킹을 더해서 이미 나왔던 최소 이동 횟수 이상이라면 해당 경우의 수와 그 이후의 경우의 수를 중간에 중지하는 방식으로 진행한다면 어느정도 가능할 것 같아서 일단 해봤다. 참고로 이 경우 모든 경우의 수는 조각이 n개 있었다면 다음과 같이 확인하면 된다. 1... 2022. 3. 21.
백준 9997 자바 - 폰트 (BOJ 9997 JAVA) 문제 : boj9997 1,2,3에 걸쳐서 점점 효율성이 좋은 풀이를 설명할 겁니다. 그러니 최종적으로는 '3'만 보셔도 되긴합니다. 왜 그렇게 설명하냐면 제가 그렇게 풀었기 때문입니다 ㅋㅋㅋ 시간 제한 딱 맞춰서 푸는건(1초제한인데 백준에서 자바로 제출할 시 '원래시간*2+1'초 이므로 자바로는 3초제한 이었어요.) 뭔가 기분나빠서 줄이다보니 줄여지네요. 1. 우선 빠듯하게 가능한 풀이 우선 모든 경우를 살펴보는게 가능할지 생각해보면, O(2^25*100*26)가 필요하다(2는 해당 문자를 사용하거나, 안하거나이고 25는 N의 최대수치, 100은 단어 길이의 최대수치, 26은 a~z 모든 문자가 포함되었는지 확인). 상당히 빠듯하긴 하지만, 어찌보면 할만해 보이므로 일단 해봤다. 이 때 단어 길이는 1.. 2022. 3. 20.
백준 3164 자바 - 패턴 (BOJ 3164 JAVA) 문제 : boj3164 우선 뭐 배열에 직접 그린 후에 직접 세는 방식은 O(X*Y) = O(10^12) 이므로 불가하다. 애초에 메모리도 엄청 많이 들 것이다. X와 Y가 최대 10^6 이므로 시간내에 풀기 위해서는 O(N)이나 O(NlogN) 급의 풀이가 필요하다. 혹시 어떻게 푸는지 감이 안왔다면 아래의 그림을 보면 바로 아! 라고 외칠 것이다. 그래프를 2개로 나눠서 보면 쉽게 풀이법을 생각해낼 수 있다. 문제에서 제시된 그래프 그대로 풀이를 찾기엔 좀 난해할 수 있지만, 아래와 같이 가로 성분과 세로 성분을 나눠서 생각해보면(세로 성분의 맨 위는 가로성분에 이미 포함된다.) 그냥 범위내에 포함되는 매번 +2씩 증가하는 기둥의 길이를 구하는 문제가 된다. 가로 기둥 최대 50만개, 세로 기둥 최대.. 2022. 3. 19.
백준 5568 자바 - 카드 놓기 (BOJ 5568 JAVA) 문제 : boj5568 우선 항상 문제를 풀 때, 그냥 무지성으로 모든 경우를 봐도 주어진 시간, 메모리 내에 가능한지부터 확인하는 습관을 들이는게 좋다. 이 문제의 경우엔 최대 10개 중 최대 4장을 선택하면 되므로, 최대 10C4번만 보면 된다. 따라서 그냥 모든 경우를 보면 된다! -> 모든 경우를 확인하려면 k번의 반복문이 필요하다. 이렇게 반복문의 개수가 고정되지 않을 때는 재귀로 짜면 매우 편하다. 재귀를 쓰기 싫다면 스택을 쓰면 재귀로 짠 것과 동일하게 짤 수 있다. 그럼 '만들 수 있는 정수'의 종류는 어떻게 알 수 있을까? 마찬가지로 제한 조건을 확인해보면서 생각해보면 된다. 우선 1부터 99까지의 정수이므로 0이 없어서, 숫자 앞에 0이 오는 경우는 무시해도 됨을 알 수 있다. 그리고 .. 2022. 3. 16.
백준 14472 자바 - 休憩スペース (Refreshment Area) (BOJ 14472 JAVA) 문제 : boj14472 N, M, D 모두 최대 100 까지이므로 모든 경우를 다 살펴본다 해도 O(2NMD) 정도이다(2는 가로, 세로). 그러니 그냥 어렵게 DP같은걸 끼얹을 필요 없이 그냥 브루트포스를 활용한 구현문제로 보면 된다. 가로, 세로 좌표 [0~N-D, 0~M-D] 의 모든 지점에 대해서 그 우측으로 D번동안 장애물이 없다면 성공, 마찬가지로 아래쪽으로 D번 동안 장애물이 없다면 성공으로 치면 된다. 이하 그림에서는 N=3, M=3, D=2 인 경우 나올 수 있는 모든 경우를 그려보았고 그 중 장애물에 걸리지 않은 경우를 노란색, 걸린 경우를 회색으로 나타냈다. 이걸 코드로 구현만 하면 된다! 코드 : github import java.io.BufferedReader; import ja.. 2022. 3. 11.
백준 18295 자바 - Ants (BOJ 18295 JAVA) 문제 : boj18295 100자리 수가 입력으로 들어오는 것은 의미가 없다. 어차피 N이 최대 10^6 이므로, 아무리 커봐야 출력의 최대치는 10^6+1 가 될 것이다. 따라서 입력으로 들어온 수가 10^6 이외의 7자리 이상의 수라면 그냥 무시하면 되므로 100자리에 겁먹을 필요는 없다. 또한 음수도 그냥 바로 무시하면 된다. 이와 같이 한다면 그냥 String으로 받고 음수 및 7자리 이상의 판단은 간단히 되므로 BigInteger로 받지 않고도 입력받은 수를 정수로 표현할 수 있다. 따라서 굳이 HashSet 등을 쓰지 않고도 10^6+1 까지를 표현할 수 있는 배열로 체크할 수 있다. 이 문제에서 맞왜틀을 좀 외쳤는데, 'simply picks the first natural number'라고.. 2022. 3. 6.
백준 16951 자바 - 블록 놀이 (BOJ 16951 JAVA) 문제 : boj16951 1. 우선 제한을 한번 봐보자. A_i가 최대 1000인데 N과 K도 최대 1000이다. 그럼 N이 1000이고, K도 1000이라면 A_1000은 못해도 1+999x1000은 되어줘야 하는데 A_i의 최대값은 1000이다! 그러니 좀 헷갈릴 수 있는데, 그냥 주어진대로 생각해보면 된다. 결국 저건 문제 난이도를 떨어뜨리기 위한 조건으로 결국 A_1의 값이 1~1000이라는 말과 마찬가지가 된다. 2. '1'이 그래서 무슨 의미임? 이 문제에서 각 A_i의 값을 다음과 나타낼 수 있다. 그리고 A_1의 값은 제한에 의해 1~1000으로 고정된다! 따라서 A_1을 1~1000까지 중 하나로 고정시켰을 때, 주어진 A_i들이 가장 많이 들어맞는 경우를 찾으면 답을 구할 수 있다는 얘.. 2022. 3. 5.
백준 11292 자바 - 키 큰 사람 (BOJ 11292 JAVA) 문제 : boj11292 각 TC마다 N개를 모두 입력받기 전에는 뭐를 출력해야할지 알 수 없다. 또한 입력이 들어온 순서를 유지해야 하므로 정렬해서 처리할 수도 없다. 그렇다면 전부 어딘가에 저장하면서 입력받는다. 이 때 입력받으면서 최대값을 확인한 후, 다시 순회하며 최대값에 부합하는 String을 출력해주면 된다. 이 경우 O(N+N)이 된다. 내 경우엔 ArrayList를 두고 최대값이 갱신되면 리스트를 초기화하는 방식을 택했다. 즉, 현재 최대값과 동일한 값이 들어오면 ArrayList에 String을 추가하고, 최대값보다 낮으면 무시하고, 최대값보다 크면 리스트를 초기화하고 현재 최대값도 갱신하면서 새로 만들어진 리스트에 String을 추가한다. 이 경우 O(N)이 된다. 메모리도 덜쓴다. 사.. 2022. 2. 14.
백준 11653 파이썬 - 소인수분해 (BOJ 11653 Python) 문제 : boj11653 소수들로 소인수 분해 후 그 결과를 오름차순으로 출력하면 되는 문제이다. 바로 생각날 부분은 우선 소인수 분해를 위한 소수를 구하기 위해 에라토스테네스의 체를 사용해 N이하의 소수를 구한 후, 작은 소수부터 차례대로 나눠보면서 나눠지면 출력하는 방식이다. 하지만 에라토스테네스의 체를 계산하는데도 사실 O(N)정도의 시간이 필요하며, 이 문제에서는 N이 하나만 주어지므로 굳이 사용하지 않아도 된다. 만약 TC가 여러개였다면 물론 미리 소수를 구해두는게 이득이었을 것이다. 이 문제의 경우 그냥 2부터 N까지의 수로 직접 N을 나눠보면서 나눠지는 수를 출력하기만 하면 된다. 코드 : github import sys input = sys.stdin.readline n = int(inpu.. 2022. 2. 10.
백준 1544 자바 - 사이클 단어 (BOJ 1544 JAVA) 문제 : boj1544 최대 50길이의 String이 최대 50개 주어진다. 그럼 매번 단어가 주어질 때 마다 해당 단어의 사이클 단어를 전부 미리 만들어둔다고 해도, 최대 50x50 = 2500개의 단어밖에 나오지 않는다! 따라서 그냥 복잡하게 생각할 것 없이 2500개를 전부 만들면서 모든 단어끼리 비교해보면 된다. 로직은 다음과 같다. 1. n개의 ArrayList를 생성한다. 2. i번째 단어를 입력받을 시 i번 단어로 만들 수 있는 모든 사이클 단어를 만들어서 i번째 ArrayList에 집어넣는다. 3. 1번째부터 i-1번째 ArrayList들을 각각 전부 순회하며 동일한 단어가 있었는지 확인한다. 4. '3'에서 없었다면 cnt를 1 증가시킨다. i를 1 증가시키며 i가 n이 될때까지 2~4를.. 2022. 2. 9.

티스토리툴바