본문 바로가기

PS831

백준 23256 자바 - 성인 게임 (BOJ 23256 JAVA) 문제 : https://www.acmicpc.net/problem/23256 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/23200/BOJ_23256.java 규칙성을 찾기가 난해했다. 일단 결과부터 말하자면 이 문제는 점화식 2개를 만들어 풀어야 한다. 전체 경우의 수를 따로 세고, 전체의 경우 중 맨 우측이 1칸짜리 블록인 경우를 따로 세야 한다. 예를들어 N=1인 경우 전체 경우의 수는 7이고, 맨 우측이 1칸짜리 블록인 경우 3가지로 다음과 같다. 그럼 왜 그렇게 해야하는지 풀이를 써보겠다. 1. N=2 이상일 경우 이전 경우에서 우측에 3개가 추가된다. 이 때 그 3개는 다음의 3가지 경우가 있다. 따라서 일단 f(n)이.. 2021. 10. 21.
백준 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.
[자바] 프로그래머스 - 3 x n 타일링 [코딩테스트 연습 Lv4] - 문제 출처 : 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges - 지형이동 문제 : https://programmers.co.kr/learn/courses/30/lessons/12902 - 코드 : 깃헙 일반적으로 DP 기본 문제로 풀어봤을 2 x n 타일링과 크게 다르지 않다. 2 x n 타일링에서 규칙성이 좀 더 찾기 어려워졌을 뿐 마찬가지로 꼼꼼하게 규칙성만 잘 찾으면 된다. 1. 우선, 2칸짜리 타일을 사용해야 하므로 무슨짓을 하던 n이 홀수라면 전체 칸 수(3 x n)가 홀수이므로 2칸짜리 타일로 타일링이 불가능하다. 즉, n이 짝수일 때만 타일링이 가능하다. 이 부분은 예외로 처리해준다. (코드 10line) 2. 가장 기본적인 .. 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.

티스토리툴바