본문 바로가기

브루트포스88

[자바] 백준 9288 - More Dice (boj java) 문제 : boj9288 'In each pair, the die values should be ordered from lowest to highest'와 'Only list unique dice combinations'에 따라 이하의 로직으로 확인하면 된다! for 1번 주사위를 1부터 6까지 증가시키면서 : for 2번 주사위를 1번 주사위의 현재 눈금 이상부터 6까지 증가키시면서 : 1번 주사위와 2번 주사위의 합이 입력으로 받은 합계인 경우 1번주사위, 2번주사위 순서로 출력한다.; 위와 같이 진행하면 문제의 조건을 지키면서 brute force로 모든 경우를 확인할 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStrea.. 2022. 7. 11.
[자바] 백준 23817 - 포항항 (boj java) 문제 : boj23817 상당히 좋은 아이디어 문제라 생각한다. 얼핏 브루트포스 문제로 생각하기 힘들고, 당연히 bfs로 어떻게든 잘 해야 할 것 같이 생겼다. 하지만 잘 생각해보면 단순 탐색으로는 최소시간을 찾기 힘들고 모든 경우의 수를 보는 brute force(완전탐색)로 봐야할 것임을 알 수 있다. 로직을 나눠서 생각해보자. 1. 최대 20개의 식당에 대해 5개의 식당을 방문하는데 필요한 최소한의 시간을 구할 수 있어야 한다. 이걸 확인하려면 기본적으로 방문 순서도 중요하다. 즉 20C5가 아니라 20P5로 봐야 한다. -> 모든 정점 사이의 거리를 안다면 1000x1000 짜리 배열이 아니라 최대 21개(S가 1개, K개 20개)의 정점과 그 사이에 거리에 관한 간선이 있는 그래프로 변경할 수 .. 2022. 6. 25.
[자바] 백준 2154 - 수 이어 쓰기 3 (boj java) 문제 : boj2154 n이 최대 100000이므로, 모두 이어쓴다고 해도 500000개 이하 정도 수준의 character 수로 구성될 것이다. 따라서 직접 해당 문자열을 만들어주고, 문자열에서 n을 찾아줘도 시간내에 통과 가능하다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); StringBuild.. 2022. 6. 11.
[자바] 백준 9715 - 면적 구하기 (boj java) 문제 : boj9715 이하의 예시를 확인해보자. 2 3 312 103 그림으로 그려보면 아래와 같다. 면적, 즉 다른 상자에 닿아있지 않고 공기(?)와 닿아있는 면의 수를 세면 될 것이다. 우선 어떻게 해야 면적을 구할 수 있을지 생각해보자. 우선 가장 간단한 바닥에서 위로 본 형태와, 위에서 바닥쪽으로 본 형태부터 생각해보자. 둘 다 아래와 같이 2차원 평면의 형태로 보일 것이다. 따라서 0이 아닌 위치라면 면은 항상 +2를 해주면 된다(바닥 하나 뚜껑 하나). 그럼 이제 동서남북 4개의 방향에서 공기와 닿아있는 면을 세주면 된다. 우측에서 좌측으로 보는 경우를 한번 생각해보자. 아래 그림과 같은 방향이다. 설명을 돕기 위해 판이 하나 이동하면서 본다고 해보면, 아래와 같은 두 가지 부분에서 면이 공.. 2022. 5. 31.
[ABC252] C - Slot Strategy (AtCoder Beginner Contest 252 in Java) 문제 : abc252_c arr[a][b]는 a라는 수(016(=6+10)으로 눌러야 하므로 16초가 필요하다. arr[1]의 경우엔 0->1->7이므로 7초, arr[2]는 0->2->9이므로 9초... 이런식이다. 이 중 가장 작은 것은 arr[8]로 0->2->6으로 6초가 된다. 이런식으로 arr[a][b]를 구해둘 시 arr[0]~arr[9] 각각의 초를 구하고, 그 중 가장 작은 초를 출력해주면 된다. 코드 : github ... private int getTime(int[] cnt) { int max = 0; for (int i = 0; i < 10; i++) { int calc = i+(cnt[i]-1)*10; max = Math.max(calc, max); } return max; } p.. 2022. 5. 22.
[ABC252] B - Takahashi's Failure (AtCoder Beginner Contest 252 in Java) 문제 : abc252_b N개의 입력값 중 가장 큰 수를 제외한 데이터는 의미가 없다. 결국, N개의 입력값 중 가장 큰 수의 인덱스들이 K개의 입력값 중에 포함된다면 Yes, 아니라면 No를 출력해주면 되는 문제이다. 따라서 내 경우엔 N개를 입력받으면서 max 값을 찾는다. 이 때 새로운 max값이 나타난다면 HashSet을 초기화하고, max값과 동일한값이 나타날 시 HashSet에 추가하는 식으로 진행했다. 이후 K개를 입력받으면서 HashSet에 있는지만 판단해줬다. 코드 : github ... private void solution() throws Exception { int n = nextInt(); int k = nextInt(); HashSet hs = new HashSet(); int .. 2022. 5. 22.
[자바] 백준 25194 - 결전의 금요일 (boj java) 문제 : boj25194 우선 문제를 이해했다면, N개의 정수에서 1~N개를 더한 여러 경우의 수 중 7로 나눈 나머지가 4가 되는 경우가 있는지 찾는 문제라고 이해할 수 있다. 하지만 이걸 구하는 방법을 찾긴 좀 어려웠다. 단순히 찾아보면 O(1000!) 이기 때문에 말도 안되는 경우의 수가 나오기 때문이다. 내 기본 아이디어는 나머지 연산의 분배법칙을 활용하는 것이었다. 나머지 연산의 경우 다음의 분배법칙을 따른다. 즉, 100000이하의 큰 'A일'들이 입력으로 들어오지만, 결국 그냥 미리 7로 나눠놔도 결과를 구하는데에 지장이 없다는 얘기이다. 또한 7로 나눈 나머지가 0이 되는 경우는 아예 필요가 없는 경우이다(원점임). 따라서 버려준다. 그렇게 되면 이 문제는 1~6 까지의 숫자가 각각 여러개.. 2022. 5. 16.
[ABC251] C - Poem Online Judge (AtCoder Beginner Contest 251 in Java) 문제 : abc251_c 만약 공통된 String 부분이 없다고 생각해보자. 그럼 단순히 입력 중 최대 T값이 인덱스를 출력해주면 될 것이다. 다만 이 문제에서는 S를 기준으로 중복된 값이 들어왔다면 해당 값은 무시해줘야 한다. 동일한 String이 들어왔는지 확인하는 가장 간단한 자료구조는 HashSet을 사용하는 것이다. 따라서 HashSet으로 이미 들어온 값이라면 무시하고, 그렇지 않다면 HashSet에 등록하고 최대값인지 체크하면 된다. 코드 : github ... private void solution() throws Exception { int n = nextInt(); HashSet hs = new HashSet(); int max = 0; int maxIdx = 0; for (int i .. 2022. 5. 15.
[ABC251] B - At Most 3 (Judge ver.) (AtCoder Beginner Contest 251 in Java) 문제 : abc251_b 1~3개의 합이 W이하인지 확인하는 문제이다. 최소 1개, 최대 3개를 모두 골라보면 된다. 따라서 모든 경우를 확인하는데 O(N^3)이 필요하며, N이 최대 300개이므로 시간은 널널하다. 중간에 합이 W보다 커지는 경우 해당 경우를 확인하지 않는 백트래킹 개념도 더하면 더 효율적으로 짤 수 있다. 주의점은 모든 경우 중, W이하를 만족하는 모든 경우를 구하는게 아니라 그러한 합계를 구해야 한다. 따라서 HashSet 등을 통해 중복된 값은 카운팅 하지 않도록 별도로 처리가 필요하다. 코드 : github ... int n, w, ans=0; int[] arr; boolean[] v; HashSet hs = new HashSet(); private void proc(int id.. 2022. 5. 15.
[자바] 백준 13552 - 구와 쿼리 (boj java) 문제 : boj13552 처음엔 시간 제한을 안보고 다음과 같이 생각했다. x,y,z값을 sqrt(1000000)정도씩 구간을 나눠서 연산을 줄이면 어찌저찌 되지 않을까 싶었다. 하지만, 시간 제한을 보니 출제 의도가 그냥 한번 해보라는 것 같았다. 모든 경우를 살펴본다고 하면, O(NM)으로 사실 무리가 있을 것 같긴 했는데, 시간 제한이 20초나 되므로 일단 해보기로 했다(자바의 경우 주어진 시간 x2+1초 이므로 총 41초 제한이다.). 그래도 만만치 않은 수치이므로 입출력 모두 빠르게 되도록 짰고, 연산이 느리고 불명확해서 틀릴 가능성이 있는 double을 사용하지 않도록 짰다. 참고로 3차원에서 두 점 (a,b,c), (x,y,z)의 거리는 (A)와 같이 구할 수 있다. 이 문제에서는 반지름이 .. 2022. 5. 13.