본문 바로가기

BOJ749

[자바] 백준 1010 - 다리 놓기 (boj java) 문제 : boj1010 해설은 다음과 같다! 결론은 mCn을 구하면 된다. 코드에서 n = Math.min(n, m-n)은 mCn = mCm-n를 코드로 나타낸 것이다. 일단 연산 도중에 long의 범위를 넘어갈 수 있다. 간단하게는 코드처럼 BigInteger로 처리하면 되고, 사실 n과 m이 그리 크지 않으므로 오차만 적당히 조정해주면 double로 연산해도 통과할 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.math.BigInteger; import java.util.StringTokenizer; public class Main { private void solution() .. 2022. 5. 20.
[자바] 백준 24479 - 알고리즘 수업 - 깊이 우선 탐색 1 (boj java) 문제 : boj24479 단순한 dfs 문제로 보이겠으나, 문제는 '오름차순' 부분이다. 이걸 위해 인접 행렬로 간선을 저장할 경우 O(N^2)이 필요하므로 시간초과가 나게 될 것이다. 그러니 인접 리스트로 간선을 표현하는게 좋고, 미리 오름차순으로 각 정점의 간선들을 정렬시켜두면 이 문제에서는 인접 행렬의 경우보다 시간도 덜 들고 메모리도 덜 들어 더 효율적으로 짤 수 있다. 위의 전처리 이외에는 기본 DFS로 구현하면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.Stri.. 2022. 5. 18.
[자바] 백준 1115 - 순열 (boj java) 문제 : boj1115 오랜만에 엄청 잘만들었다고 느낀 문제였다. 아이디어 문제이다. 해설은 간단한데, 사실 이걸 떠올리는게 전부인 문제이다. 1. B[0] = 0 이므로 즉 A[0]부터 시작한다고 보면 된다. 2. B[i]=A[B[i-1]] 은 즉 A[0]부터 시작한댔으니, A[0] -> A[A[0]] -> A[A[A[0]]] 이런식으로 진행하겠다는 의미이다. 이 때 이게 순열이 되려면 결국 중간에 끊기지 않고 모든 A원소들을 들릴 수 있어야 한다. 그럼 당연히 처음 입력된 A가 모두 들릴 수 있다면? 그냥 0으로 끝이다. 중요한건 중간에 끊길 경우, 어떻게 최소로 교환해서 전체를 들릴 수 있도록 만들 것인지가 관건이다. 직관적으로 이걸 그래프로 생각해보면 좀 더 생각하기 편한데, 결국 끊겼다는 것은 .. 2022. 5. 17.
[자바] 백준 25200 - 곰곰이와 자판기 (boj java) 문제 : boj25200 에디토리얼과도 아예 다른 풀이이고, 난이도 기여의 다른 사람들 의견과도 다른 방식인걸로 보아 상당히 독특하게 푼 것 같다. 당연히 N개의 음료수에 대해 M번의 차원 이동을 실제로 해보려면 현재 이동할 차원 U, V(3, 3->2 라면 1->3으로 차원3에는 1과 3의 두개가 있을 것이다. 따라서 3->2는 3만 이동하면 안되고 1과 3을 둘 다 이동해야 한다. 그러므로 O(NM)의 시간복잡도가 필요하므로 통과할 수 없다. 그렇다면, 첫 시작을 N개의 LinkedList로 해보면 어떨까? LinkedList[N+1] 짜리에 각각 LinkedList[1]엔 1만 있고, [2]엔 2만 있고, ... [N]엔 N만 두고 시작해보자. 그럼 M개의 쿼리에 대해 U->V로 빠르게 Linked.. 2022. 5. 16.
[자바] 백준 25195 - YES or yes (boj java) 문제 : boj25195 그래프 탐색에 대해 단순하게 DFS, BFS만 익힌게 아니고 이해하고 있다면 사실 엄청 쉬운 문제이다. 결국 DFS(깊이 우선 탐색)으로 진행하면서 팬을 만나지 않고 더이상 진행할 간선이 없는 곳에 도착하는지만 보면 된다. 주의할 점은 방문체크를 두면 안된다. 왜냐면 이미 팬을 만난채로 진행한 경로라서 방문체크가 됬더라도 팬을 만나지 않은채로 진행이 가능해야 하기 때문이다. 이럼 사실 방문체크를 하되, 팬을 만나고 도착했는지 팬을 안만나고 도착했는지에 따라 dp를 좀 끼얹어서 그래프 탐색을 해도 되긴한다. 근데 어차피 DAG(Directed Acyclic Graph. 사이클 없는 방향그래프)이므로 팬을 만났다면 바로 back tracking으로 이전으로 돌아가기만 해도 된다. 이.. 2022. 5. 16.
[자바] 백준 25194 - 결전의 금요일 (boj java) 문제 : boj25194 우선 문제를 이해했다면, N개의 정수에서 1~N개를 더한 여러 경우의 수 중 7로 나눈 나머지가 4가 되는 경우가 있는지 찾는 문제라고 이해할 수 있다. 하지만 이걸 구하는 방법을 찾긴 좀 어려웠다. 단순히 찾아보면 O(1000!) 이기 때문에 말도 안되는 경우의 수가 나오기 때문이다. 내 기본 아이디어는 나머지 연산의 분배법칙을 활용하는 것이었다. 나머지 연산의 경우 다음의 분배법칙을 따른다. 즉, 100000이하의 큰 'A일'들이 입력으로 들어오지만, 결국 그냥 미리 7로 나눠놔도 결과를 구하는데에 지장이 없다는 얘기이다. 또한 7로 나눈 나머지가 0이 되는 경우는 아예 필요가 없는 경우이다(원점임). 따라서 버려준다. 그렇게 되면 이 문제는 1~6 까지의 숫자가 각각 여러개.. 2022. 5. 16.
[자바] 백준 25193 - 곰곰이의 식단 관리 (boj java) 문제 : boj25193 결국 중요한건 음식의 리스트를 '원하는 대로' 조정할 수 있다는 점이다. 그럼 'CCCCA' 와 같은 경우를 생각해보자. 어떻게 해야 연속된 C의 최댓값을 최소화시킬 수 있을까? 'CCACC'처럼 A로 나누면 된다. 'CCCCCAB'와 같은 경우엔 어떨까? 마찬가지로 최대한 C를 그 이외의 음식으로 잘게 나누어야 한다. 'CCACCBC'처럼 나누면 될 것이다. 그렇다면, C의 개수를 C가 아닌 것들의 개수로 나누면 될 것임을 알 수 있다. C가 아닌 것을 A라고 한다면 다음과 같은 식을 계산하면 된다(|X|는 X의 개수를 의미함). +1을 한 이유는 예를들어 1개의 벽으로 나눌 수 있는 구역은 2개이고, 2개의 벽으로는 3개가 된다. 그때문에 +1을 해준 것이다. 올림을 하는 이.. 2022. 5. 16.
[자바] 백준 25192 - 인사성 밝은 곰곰이 (boj java) 문제 : boj25192 'ENTER'가 나온 후 새로 나온 String의 수를 세면 된다. 이 때, ENTER가 나오면 '새로 나온'이 리셋된다고 생각하면 된다. 즉, ENTER A ENTER A 라면 A는 중복이지만 ENTER일 때 초기화됬으므로 2가 답이 된다. 반면에 ENTER A A 라면 A가 중복되므로 1이 답이 된다. 따라서 필요한건 빠른 시간 내에 String이 중복되었는지 확인할 수 있는 자료구조 혹은 알고리즘이다. HashSet이 딱이므로 HashSet을 사용해서 짜주면 된다. 코드 : github ... private void solution() throws Exception { int n = nextInt(); int cnt = 0; HashSet hs = new HashSet();.. 2022. 5. 16.
[자바] 백준 25191 - 치킨댄스를 추는 곰곰이를 본 임스 (boj java) 문제 : boj25191 만약 콜라, 맥주가 매우 많다하더라도 N보다 더 많이 시킬수는 없다. 또한 N이 충분하더라도 A/2+B ('콜라 2개나 맥주 1개' 이므로 콜라/2의 수와 맥주의 수를 더한다.) 보다 더 많이 시킬수는 없다. 따라서 min(N, A/2+B)를 출력해주면 된다. 코드 : github ... private void solution() throws Exception { int n = nextInt(); int a = nextInt(); int b = nextInt(); int cnt = a/2+b; System.out.println(Math.min(n, cnt)); } ... 2022. 5. 16.
[자바] 백준 14426 - 접두사 찾기 (boj java) 문제 : boj14426 정해는 대놓고 Trie 쓰라고 낸 거 같은 문제이다. 하지만 N, M, 문자열의 길이가 애매하게 적고 메모리가 상당히 많다. 그래서 밑져야 본전이니 메모리를 많-이 써서 한번 해보고 통과하면 통과되는거고, 안되면 Trie 쓰려고 했는데 이렇게 썼단 이유는 됬다는 그런 얘기이다. 일단 단순히 브루트포스로 풀려고 하면 O(500xNxM) 이므로 불가하다. 하지만 메모리를 더 써서, 미리 N개에 대해 접두사 HashSet을 만들어두면 어떨까? 이 경우 String이라 hash function에 다소 부하는 걸리겠지만, 대강 O(1)이라고 치면 O(500N + M) 으로 가능하다. hash function의 부하를 생각해도 대강 통과는 될 것 같아서 해봤다. 추가로 약간이라도 hash .. 2022. 5. 16.

티스토리툴바