본문 바로가기

PS/BOJ764

백준 1270 자바 - 전쟁 - 땅따먹기 (BOJ 1270 JAVA) 문제 : https://www.acmicpc.net/problem/1270 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01200/BOJ_1270.java 실3지만, 자바로는 메모리초과 때문에 개인적으로 골드 상위정도는 될 듯 하다. 일단 자바로 성공한게 현재로썬 혼자뿐이다. 문제 자체는 그냥 카운팅만 잘 하면 되는 쉬운 문제이므로 해설은 이 문제를 자바로 도전할 사람들을 위해 메모리를 감소시킨 방식과 일부 이해하기 힘들 수 있는 코드 부분에 대해 적어본다. 1. 일단 입력 최대치가 2^31-1이 아니고 int형 범위를 1 넘어간 2^31 이라는 점에서 악의성이 다분하다. 그냥 대충 해싱으로 t개 전부 카운트 하려 했더니 메모리 .. 2021. 10. 21.
백준 16497 자바 - 대출 요청 (BOJ 16497 JAVA) 문제 : https://www.acmicpc.net/problem/16497 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/16400/BOJ_16497.java 이 문제의 경우, 31일까지 모든 날짜에 대해 현재 대출되어 있는 책의 수를 세보면 간단히 풀 수 있다. 이 때 주의점은 (3, 6)이라면 3일에 빌려서 6일 0시에 딱 반납된다고 생각하면 된다. 즉, (3, 6)과 (6, 8)이 있다면 k=1 일때도 처리할 수 있다는 의미이다. 따라서 (3, 6)이라면 3일에 빌려서 5일까지만 가지고 있다고 생각하면 된다. 그럼 문제에 나온 기본 예시 (1, 2), (3, 6), (5, 8)은 다음과 같이 나타낼 수 있다. 이와 같이 모든.. 2021. 10. 19.
백준 16666 자바 - Guest Student (BOJ 16666 JAVA) 문제 : https://www.acmicpc.net/problem/16666 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/16600/BOJ_16666.java 어렵진 않고 그냥 수학적으로 생각해서 구현하면 되는거긴한데.. 코드보면 알겠지만 이래놓고 실버라니 숭악하다. 0. 일단 매 TC 마다 입력을 받아두고(14line), 1로 시작하는 위치에서 모두 시작해본다. (15~16line) 1. 거기서 부터 일단 k가 0이될 때 까지 돌려본다.(19~22line) -> 이 때 k가 0이 된다면 그걸로 해당 회차는 끝 (23line) -> 그렇지 않다면 다음 로직으로 2. 다음으로 중간 부분은 수학적으로 나눗셈을 활용해서 날려버릴 수 있.. 2021. 10. 18.
백준 11376 자바 - 열혈강호 2 (BOJ 11376 JAVA) 문제 : https://www.acmicpc.net/problem/11376 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/11300/BOJ_11376.java 기본적인 형태의 이분 매칭 문제이다. 다만 한 사람당 2개의 일을 할 수 있으므로, n을 2배로 늘렸다. 이 때 간선 정보는 n개만 유지할 수 있도록 하는것이 좋다. 내 경우엔 그래서 간선정보를 n개 받아두고, e[n/2] (12line) 형태로 받아온다. 사실 이분 매칭에서 매칭시킬 때, 기본형태에서 그 안에 들어있는 n의 번호 자체는 중요한게 아니므로(같던 다르던 상관 없음) 코드의 45line처럼 for문 돌릴 필요 없이, 그냥 그 내에서 다시한번 2번을 돌리도록 해도.. 2021. 10. 17.
백준 11375 자바 - 열혈강호 (BOJ 11375 JAVA) 문제 : https://www.acmicpc.net/problem/11375 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/11300/BOJ_11375.java 이분매칭에 응용같은걸 끼얹지 않은 기본형 문제이다. 따라서 단순히 '이분 매칭'을 공부해서 풀어도 바로 풀 수 있으며, 아이디어에 대한 힌트만 보려면 이 글(https://nahwasa.com/36)의 하위호환이므로, 이 글의 그림 있는 부분부터 보면 이 문제의 풀이 방식과 동일하다. 빨리 각 알고리즘이나 자료구조들에 대한 글을 써서 그런걸로 링크를 달면 깔끔할텐데.. 그런거 쓰려면 한편한편이 너무 오래걸린다 ㅠ 열심히 해야지.. 2021. 10. 16.
백준 18138 자바 - 리유나는 세일러복을 좋아해 (BOJ 18138 JAVA) 문제 : https://www.acmicpc.net/problem/18138 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/18100/BOJ_18138.java 일단하나씩 매칭시키는 문제이니 이분 매칭 문제인건 알겠는데, 그래프에 간선이 없다. 그러니 로직은 간단히, 1. 입력을 받는다 (init()) 2. 간선을 만든다 (makeEdge()) -> 이 때, w가 동일한게 안들어온다는 보장이 없으므로 w 대신 인덱스 번호로 새로 매칭시킨다. n개와 m개에 대해 0~n과 0~m을 노드로 하는 그래프로 바꾸면 된다. 간선을 만든 이후 w값은 필요없어진다. (62line) 3. 이분 매칭 돌린다 (matching()) 이분 매칭의 경우,.. 2021. 10. 16.
백준 14217 자바 - 그래프 탐색 (BOJ 14217 JAVA) 문제 : https://www.acmicpc.net/problem/14217 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/14200/BOJ_14217.java 문제 길이에 비해 사실 생각보다 쉬운 문제이다. 결국 시간복잡도가 문제인데, 가장 쉽게 생각할 수 있는 방법은 그냥 무작정 q줄에 대해 매번 해당 edge를 추가하거나 제거한 후 최단거리를 찾아보는 방식이다. 그럼 최단거리 찾기에 가장 간단한 bfs부터 보자. O(V+E) 정도이므로, O(N^2)정도고, q가 최대 500번이므로 최종적으로 최악의 경우 O(500^3) 정도로 별 문제가 없다는걸 알 수 있다. 그러니 그냥 입력 쫙~ 받고 q줄에 대해 매번 간선을 제거하거나 추.. 2021. 10. 14.
백준 1412 자바 - 일방통행 (BOJ 1412 JAVA) 문제 : https://www.acmicpc.net/problem/1412 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01400/BOJ_1412.java 플래 중위권 문제치곤 그리 어렵지 않았다. 구현이 어렵다기보다는 아이디어를 떠올리기 좀 어려울 수 있는 문제라 티어가 높게 책정된 듯 하다. 일단 '도시 x에서 출발해서 다시 그 도시 x로 돌아올 수 없게 만드는 것이다.' 부분을 만족하려면, 결국 자기 자신으로 되돌아오는 Cycle이 없으면 된다. 여기까진 쉽게 생각할 수 있는데 그럼 양방통행와 일방통행 도로의 두 종류가 있는 상황에서 어떻게 해야 Cycle을 없앨 수 있는지가 관건이다. 그래서 일단 그려보며 열심히 생각해봤는.. 2021. 10. 11.
백준 3015 자바 - 오아시스 재결합 (BOJ 3015 JAVA) 문제 : https://www.acmicpc.net/problem/3015 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/03000/BOJ_3015.java 우선 체크를 어느 방향으로 할 지 정해보자. 전 왠지 입력 다 받고 풀기보단 입력 받으면서 바로바로 풀고 싶었기에 N번째 사람을 입력받을 때 그 이전사람들을 체크해보기로 했다(입력 받으면서 바로바로 하려면 그 이후 사람에 대한 정보는 없으므로 그 이전 사람들만 가지고 생각해야한다!). 방향을 저와 같이 정했다면, 이번에 입력된 사람보다 키가 작은 이전사람은 의미가 없다는 것을 알 수 있다. (위와 같이 4명까지 확인했다. 그리고 5명째를 확인하려고 하는데, 사실 이 때 N=2와.. 2021. 10. 10.
백준 15779 자바 - ZigZag (BOJ 15779 JAVA) https://www.acmicpc.net/problem/15779 i번째 데이터에 대해, i-2, i-1, i 번째 데이터를 살펴보며 단조증가 수열이거나 단조감소 수열일 경우 arr[i] = 0을 기입했고, 지그재그 수열일 경우 1을 기입함.(13line) 그럼 예를들어서 문제에 제시된 2번째 예시 (1,3,4,2,5)의 경우 제가 짠 로직으로는 arr = [0, 0, 0, 1, 1] 와 같이 기입됨. 근데 이 때 1이 연속된 갯수가 결국 지그재그 수열의 길이이므로, 13line처럼 이전값+1을 해주면 연속된 길이도 한꺼번에 구할 수 있음. 최종적으로 arr 배열에 있는 가장 큰 수가 가장 긴 지그재그 수열의 길이이므로 max값을 찾아주고 (19line) 거기에 2를 더해준게 답임. (+2를 해준 것은.. 2021. 10. 8.

티스토리툴바