본문 바로가기

PS/BOJ752

백준 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.
백준 2759 자바 - 팬케이크 뒤집기 (BOJ 2759 JAVA) https://www.acmicpc.net/problem/2759 알고리즘 분류를 굳이 따지자면 constructive, ad-hoc, greedy 쪽일 것 같음. 애초에 답으로 가능한 경우 어떤 것이든 출력하면 되기도 하고, 이런 류의 문제를 풀기위한 well-known 스러운 풀이도 없다고 판단되므로 논리적 추론을 통해 이 문제만의 풀이과정을 만들어야 하는 종류의 문제이다. Brute force로 모든 경우를 보면 최대 O(30^30) 이라는 괴랄한 수가 나오므로 절대 무리.. 전 일단 가장 큰 수 부터 차례대로 맨 아래로 가야한다는 부분에 포인트를 맞추고, 그럼 위에서 k개를 뒤집는 방식으로 어떻게 가장 큰 수부터 차례대로 맨 아래로 내릴지 생각해봤다. 결론적으로 제 풀이는 다음과 같음. 가장 큰 .. 2021. 10. 7.
백준 15993 자바 - 1, 2, 3 더하기 8 (BOJ 15993 JAVA) https://www.acmicpc.net/problem/15993 f(n)을 정수 n을 1,2,3의 덧셈으로 표현 가능한 가지수라 정의하면, f(n) = f(n-1) + f(n-2) + f(n-3) 이다. 왜냐하면 예를들어 n=5라면, f(5)는 f(4)의 모든 표현의 뒤에 +1을 붙인 것 + f(3)의 모든 표현의 뒤에 +2를 붙인 것 + f(2)의 모든 표현의 뒤에 +3을 붙인 것 이기 때문이다. 위 식을 배열로 나타내자면 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]; 이 된다. 그런데 이상태로는 짝수가지수와 홀수가지수를 알 수 없다. 따라서 dp를 2차원 배열로 확장해서 dp[a][b]로 보자. a가 1,2,3의 합으로 나타내려는 정수, b는 0일 때 짝수인 경우, 1일 때 홀.. 2021. 10. 7.

티스토리툴바