곰곰컵6 [자바] 백준 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. 이전 1 다음
