본문 바로가기

백준757

[자바] 백준 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.
[자바] 백준 24155 - 得点 (Score) (boj java) 문제 : boj24155 다음의 표를 보자. (A)는 애초에 입력이 내림차순이고 겹치는 점수가 없는 경우이다. 이 경우 등수는 순서대로가 될 것이다. (B)는 내림차순이지만, 겹치는 점수가 있는 경우이다. 이 경우 이전과 점수가 같다면 등수도 이전과 동일하고, 이전과 점수가 다를 경우 현재 자신의 위치를 출력하면 순서대로 등수를 출력할 수 있다. 이 문제의 경우 처음에 정렬이 되어 들어오지 않는다. 따라서 (C)와 같이 정렬한 후 등수를 매겨보자. (A), (B)와 달리 '학생'부분의 숫자가 뒤죽박죽인 것을 알 수 있다. 정렬 후 등수를 매기는 것은 (A), (B)와 동일하다. 이후 (D)와 같이 학생 번호 순서대로 다시 정렬하면 처음 입력된 순서대로 등수를 출력할 수 있다. 코드 : github imp.. 2022. 5. 15.
[자바] 백준 10025 - 게으른 백곰 (boj java) 문제 : boj10025 x는 0부터 1000000까지의 좌표값이다. 그리고 [x-k, x+k] 구간내에 있는 얼음의 합을 구할 수 있다면, 모든 구간을 보면서 최대치만 찾으면 된다. 슬라이딩 윈도우 혹은 prefix sum을 계산해서 구하면 된다. prefix sum으로 할 경우, 좌표별로 prefix sum 배열(이하 ps[])을 만들고 이후 좌표 a에서 잡을 수 있는 얼음의 합은 ps[a+k]-ps[a-k-1]가 될 것이다. 따라서 a를 k부터 n-k까지 증가시키면서 각 O(1)로 a 위치에서의 얼음의 합을 구할 수 있으므로 O(|x|) (x의 크기는 1000000)으로 답을 구할 수 있다. 이하 코드는 슬라이딩 윈도우 방식으로 짠 코드이다. 슬라이딩 윈도우도 비슷하다. a를 k부터 n-k까지 증가.. 2022. 5. 14.
[자바] 백준 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.
[자바] 백준 14425 - 문자열 집합 (boj java) 문제 : boj14425 해쉬에 대한 개념을 알고, HashSet 자료구조를 알고 있다면 간단하게 풀 수 있다. N개를 HashSet에 넣고, M개를 입력받으면서 HashSet에 존재하는지 확인하면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashSet; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTok.. 2022. 5. 13.

티스토리툴바