브루트포스91 [자바] 백준 12100 - 2048 (Easy) (boj java) 문제 : boj12100 (상당히 귀찮은편인) 단순 시뮬레이션 문제이다. 최대 5번 이동이라고 했으므로, 처음 상태에서 상하좌우 4방향으로 움직이는걸 최대 5번 반복하면 된다. 즉, 최대 4^5번으로 모든 경우를 확인할 수 있다. 이 때 각 방향마다 NxN 칸의 모든 것들을 해당방향으로 움직여야 한다고 볼 수 있으므로 대략 O(N^2 x 4^5)의 시간복잡도가 된다. 그럼 남은건 상하좌우 방향으로 움직인다고 할 때, 문제에서 제시된 방법대로 동작만 되도록 시뮬레이션을 구현해주면 된다. 이 때 주의점은 예를들어 아래와 같은 경우를 보자. 2 0 0 2 0 0 2 0 0 위와 같은 경우 우측 방향으로 모두 이동시킨다고 했을 때, 우측으로 모두 붙어야 할 것이다. [A] 0 2 0 0 2 0 0 2 0 [B].. 2022. 7. 20. [자바] 백준 11648 - 지속 (boj java) 문제 : boj11648 n이 한자리 수가 될 때 까지, 각 자리수를 곱한 새로운 값을 구해 n에 넣어주면 된다. 각 자리수를 곱하는 부분은 이하 코드의 요 부분을 참고해보자. while (n!=0) { cur*=n%10; n/=10; } 코드 : 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()); int cnt =.. 2022. 7. 12. [ABC259] C - XX to XXX (AtCoder Beginner Contest 259 in Java) 문제 : abc259_c 내 경우엔 String을 다음과 같이 압축시켜서 판단했다. abbaac => a1 b2 a2 c1 abbbbaaac => a1 b4 a3 c1 위와 같이 압축시킬 경우, 다음과 같이 판단할 수 있다. 1. 압축시킨 갯수가 다를 경우 No (예를들어 a1 b2 c2 vs a1 b2 였다면 3개와 2개로 비교해볼 것도 없이 No 이다.) 2. 압축시킨 부분에서 문자 부분이 서로 다른 경우 No (예를들어 a1 b1 c1 vs a1 d1 c1) 3. 압축시킨 각 부분에서 숫자가 S를 압축시킨쪽이 더 큰 경우 No (예를들어 a2 vs a1) 4. 압축시킨 각 부분에서 숫자가 서로 다른데, S가 1인 경우 No (예를들어 a1 vs a2) 5. 이외의 경우 Yes 코드 : github .. 2022. 7. 11. [자바] 백준 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. 이전 1 2 3 4 5 6 7 ··· 10 다음
