본문 바로가기

PS/BOJ764

백준 20156 자바 - 기왕 이렇게 된 거 암기왕이 되어라 (BOJ 20156 JAVA) 문제 : boj20156 구현도 빡쌘편이고 함정카드도 꽤 생각하기 힘든 녀석이었다. 역시 항상 20퍼대 이하의 정답률 문제들은 항상 뭔가가 있다. 그리고 요즘 스트릭만 채운다고 실버위주로 풀다가 오랜만에 플래 풀어보니 체감이 확 된다 ㅋㅋㅋ 1. 우선 다른거 다 빼고 동일 스터디 그룹인지 어떻게 알 수 있을지 생각해보자. 이 부분은 간단하다. union-find를 사용해 disjoint set을 파악하면 된다. 입력으로 받은 B와 C가 동일한 그룹인지 확인하려면, B와 C가 같은 그룹내에 속한지 판단만 하면 알 수 있다(일반적으로 union-find를 사용했다면 결국 find(B) == find(C) 라면 동일 그룹이다). 2. 그룹이 해제는 어떻게 해요? 생각할게 너무 많아요! 그룹을 해제하는건 어렵지.. 2022. 3. 8.
백준 1765 자바 - 닭싸움 팀 정하기 (BOJ 1765 JAVA) 문제 : boj1765 1. '내 친구의 친구는 내 친구' + '내 원수의 원수도 내 친구' 이걸 해석은 명확히 해야한다. 우선 '내 친구의 원수'에 대한 내용은 없으니 신경쓸 필요가 없다. 그리고 '내 친구의 친구는 내 친구' 라고 했으니 내 친구라면 쭉쭉 이어나가면서 친구를 찾을 수 있음을 알 수 있다. '내 원수의 원수도 내 친구' 부분이 문제인데, 원수의 원수의 원수 이런건 생각할 필요가 없다. 딱 두 단계에 걸친 원수사이면 친구라는 말이다. 또한 첫 번째 조건과 합쳐져서, 원수의 원수의 친구 또한 내 친구이다! 원수의 원수의 친구의 친구 또한 내 친구이다! 좀 헷갈릴 수 있는데 그냥 주어진 조건 2개에 대해 여러 경우를 생각해보면 저렇게 된다. 정리해보면 - 내 원수 -> 그냥 원수임 - 내 원.. 2022. 3. 7.
백준 18295 자바 - Ants (BOJ 18295 JAVA) 문제 : boj18295 100자리 수가 입력으로 들어오는 것은 의미가 없다. 어차피 N이 최대 10^6 이므로, 아무리 커봐야 출력의 최대치는 10^6+1 가 될 것이다. 따라서 입력으로 들어온 수가 10^6 이외의 7자리 이상의 수라면 그냥 무시하면 되므로 100자리에 겁먹을 필요는 없다. 또한 음수도 그냥 바로 무시하면 된다. 이와 같이 한다면 그냥 String으로 받고 음수 및 7자리 이상의 판단은 간단히 되므로 BigInteger로 받지 않고도 입력받은 수를 정수로 표현할 수 있다. 따라서 굳이 HashSet 등을 쓰지 않고도 10^6+1 까지를 표현할 수 있는 배열로 체크할 수 있다. 이 문제에서 맞왜틀을 좀 외쳤는데, 'simply picks the first natural number'라고.. 2022. 3. 6.
백준 16951 자바 - 블록 놀이 (BOJ 16951 JAVA) 문제 : boj16951 1. 우선 제한을 한번 봐보자. A_i가 최대 1000인데 N과 K도 최대 1000이다. 그럼 N이 1000이고, K도 1000이라면 A_1000은 못해도 1+999x1000은 되어줘야 하는데 A_i의 최대값은 1000이다! 그러니 좀 헷갈릴 수 있는데, 그냥 주어진대로 생각해보면 된다. 결국 저건 문제 난이도를 떨어뜨리기 위한 조건으로 결국 A_1의 값이 1~1000이라는 말과 마찬가지가 된다. 2. '1'이 그래서 무슨 의미임? 이 문제에서 각 A_i의 값을 다음과 나타낼 수 있다. 그리고 A_1의 값은 제한에 의해 1~1000으로 고정된다! 따라서 A_1을 1~1000까지 중 하나로 고정시켰을 때, 주어진 A_i들이 가장 많이 들어맞는 경우를 찾으면 답을 구할 수 있다는 얘.. 2022. 3. 5.
백준 24039 자바 - 2021은 무엇이 특별할까? (BOJ 24039 JAVA) 문제 : boj24039 우선 연속한 두 소수를 알 수 있어야 한다. 이건 에라토스테네스의 체로 미리 특정 수까지의 소수를 구해두면 된다. 결론적으로 103까지의 모든 소수만 구하면 된다(어차피 상관없는게, 답은 무조건 있고 N보다 큰 수만 나오면 멈추면 되므로 대충 많이 구하면 된다.). 이후 연속한 두 소수를 곱해나가다가 N보다 큰 곱이 나오면 출력하면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; public class Main { private static final int MAX = 103; private int getAnswer(int n) { A.. 2022. 3. 4.
백준 2312 자바 - 수 복원하기 (BOJ 2312 JAVA) 문제 : boj2312 오랜만에 1분컷으로 푼 것 같다. 소인수분해의 결과는 결국 전부 소수가 될테니 미리 에라토스테네스의 체로 소수를 구해두고 수행하면 더 효율적이긴 하다. 하지만 N이 최대 100000이므로 2부터 N까지의 모든 수로 직접 나눠봐도 O(100000)밖에 안나온다. 따라서 그냥 brute force로 직접 나눠보면 쉽게 답을 구할 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamRe.. 2022. 3. 3.
백준 3711 자바 - 학번 (BOJ 3711 JAVA) 문제 : boj3711 g가 최대 300밖에 안되므로 모든 경우를 살펴봐도 O(G^2) 수준이라 브루트포스로 진행해도 무리없이 풀 수 있다. 즉, 1부터 시작해서 수를 점차 키워가면서 모든 값들을 실제로 나눠보고 그 나머지를 체크하면 된다. 이 때 주의점은 중복 체크라고 하면 일반적으로 해시셋을 쉽게 떠올릴텐데, 자바 한정으로 이 문제에서는 해시셋 사용 시 메모리 초과가 날 수 있다. 따라서 배열을 이용해 체크해주면 쉽게 통과할 수 있다. 내 경우엔 각 TC마다 체크용 배열을 초기화하고, 현재 나눠볼 값을 K라 할 때 메모리를 최대한 아끼기 위해 K에 따라서는 매번 초기화하지 않고 해당 K값을 기입했다. 코드 : github import java.io.BufferedReader; import java.i.. 2022. 3. 2.
백준 23394 자바 - Haja Ordenação (BOJ 23394 JAVA) 문제 : boj23394 Brute force로 생각하기 쉽지만, 사실 이 경우 10^5C2 만큼 판단해야 할 것이므로 시간내에 통과할 수 없다. 아이디어만 잘 떠올린다면 아주 간단하게 풀 수 있다. 사실 동일한 색상 2개를 고르고 교환하는 부분을 직접 할 필요가 없다. 중요한건 최종적으로 정렬된 순서로 만들 수 있냐이므로, 처음 입력으로 들어왔던 색상의 순서와 시퀀스만 가지고 정렬한 순서의 색상이 동일하다면 실제 색상 2개를 고르고 서로 교환하는 부분은 어떻게든 가능할테니 대충 퉁칠 수 있는 부분이 된다. 예를들어 예제 입력1과 2는 다음과 같다. 처음 입력으로 들어온 색상과, 시퀀스를 기준으로 정렬된 색상의 순서가 서로 다르다면 N, 동일하다면 Y를 출력해주면 된다. 코드 : github import.. 2022. 3. 1.
백준 2729 자바 - 이진수 덧셈 (BOJ 2729 JAVA) 문제 : boj2729 문제에 제시된대로 실제로 덧셈을 진행해주면 된다! 즉 문제에 나온대로 구현하면 풀 수 있다. 주의점은 입력은 0으로 시작할 수 있는데, 출력은 앞에 0이 붙으면 안된다는 점이다. 즉, '000001 00010' 이런 입력이 들어올 수 있고, 답은 '11' 로 앞의 0들을 출력하면 안된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = n.. 2022. 2. 28.
백준 2947 자바 - 나무 조각 (BOJ 2947 JAVA) 문제 : boj2947 문제에 나온대로 구현만 하면 되는 문제이다. 혹시 구현이 힘들다면 논리적으로 생각하며 어떻게 짜야 주어진 동작이 수행 가능할지 공책에 그려보거나 하면서 구현해 보자. 코드 : 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)); int[] arr = new in.. 2022. 2. 27.

티스토리툴바