본문 바로가기

브루트포스89

백준 17756 자바 - Kieszonkowe (BOJ 17756 JAVA) 문제 : boj17756 우선 NIESTETY 를 출력해야 하는 경우부터 살펴보자. 결국 n개에 대해 가장 큰 짝수를 구해야 하는데, 짝수로 만들 수 없다는 얘기는 n이 1개였고, 그 한개가 홀수인 경우 밖에 없다. 이제 전체 로직을 살펴보자. 짝수를 만들 수 있는 경우를 살펴보면 된다. 우선 짝수+짝수는 당연히 짝수이다. 홀수+홀수도 역시 짝수이다. 따라서 짝수는 그냥 넘어가면 되고, 홀수는 홀수인 것이 짝수개 있다면 짝수로 만드는데 문제가 없다. 이제 문제는 홀수가 홀수개 있는 경우인데, 이 때는 한 개의 수를 제외해야 한다. 당연히 가장 작은 홀수를 제거하는 것이 이득일 것이다. 최종적으로 전체 로직을 살펴보면 다음과 같다. 코드 : github import java.io.BufferedReader.. 2022. 3. 24.
백준 2003 자바 - 수들의 합 2 (BOJ 2003 JAVA) 문제 : boj2003 우선 i번째 수 부터 j번째 수까지의 합을 쉽게 알 수 있는 방법을 생각해보자. 누적합을 미리 구해둔다면 O(1)에 i번째 수부터 j번째 수까지의 합을 구할 수 있다. 예를들어 '4 7 2 1'을 확인해보자. 다음과 같이 누적합 배열(arr)을 마련해두면, i번째부터 j번째 수까지의 합은 arr[j]-arr[i-1]로 O(1)에 바로 구할 수 있다. 그럼 이제 합이 m이 되는 경우의 수를 구해야 한다. 더 효율적으로 하려면 투 포인터 개념을 활용하면 되지만, 이 문제의 경우 그냥 모든 경우를 확인하면 된다. 즉 i=1일 때 j=i~n의 모든 경우, i=2일 때 j=i~n의 모든 경우, ... i=n일 때 j=i~n인 모든 경우를 다 보면 된다. 코드 : github import j.. 2022. 3. 23.
백준 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.
백준 16936 자바 - 나3곱2 (BOJ 16936 JAVA) 문제 : boj16936 난이도 기여 멘트들을 보니 많은 분들이 ad hoc으로 보고 수학적으로 푼 것 같다. 3의 차수라는 내용이 많이 나오던데 솔직히 뭔지 잘 모르겠다 ㅋㅋ. 내 경우엔 수학적으로 잘 모르겠으니 그냥 무식하게 풀었다. 각 수를 하나의 정점으로 치고, 방향 그래프를 만든다. 만약 두 수 X, Y가 있고 X*2 == Y 혹은 X/3 == Y 라면 X->Y 처럼 X에서 Y로 가는 간선을 만든다. 예를들어 '예제 입력 1'에 대한 방향 그래프는 다음과 같다. 이렇게 모든 쌍에 대해 간선을 만들고 (모든 쌍이라고 해봐야 100x100개 뿐임), 모든 정점에서 출발해서 DFS를 돌린다. 어떠한 지점에서 DFS를 통해 모든 정점에 갈 수 있다면 해당 루트를 출력해주면 된다. 여기서 좀 더 효율적으.. 2022. 2. 23.

티스토리툴바