본문 바로가기

백준756

백준 6550 자바 - 부분 문자열 (BOJ 6550 JAVA) 문제 : boj6550 s쪽에 포인터를 하나 두고, t쪽에도 포인터를 하나 둔다. 이후 s쪽 포인터를 하나씩 증가시키면서, 해당 포인터가 가르키는 문자가 나올 때 까지 t 포인터를 증가시키면서 찾는다. 최종적으로 t포인터가 t를 전부 찾기 전까지 s쪽 포인터가 끝까지 도달한다면 Yes가 된다. 이하 '예제 입력 1'의 3번째 테스트 케이스를 찾는 과정을 그려봤다. s쪽 포인터가 si, t쪽 포인터가 ti 이다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void solution() throws Exce.. 2022. 3. 13.
백준 6186 자바 - Best Grass (BOJ 6186 JAVA) 문제 : boj6186 상하좌우로 인접한 풀때기들의 군락(?) 수만 잘 구하면 된다. 그러니 일단 입력받고, 방문체크 하면서 dfs 돌리며 수를 세면 쉽게 구할 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void dfs(int r, int c, boolean[][] arr) { for (int dr = -1; dr 2022. 3. 12.
백준 14472 자바 - 休憩スペース (Refreshment Area) (BOJ 14472 JAVA) 문제 : boj14472 N, M, D 모두 최대 100 까지이므로 모든 경우를 다 살펴본다 해도 O(2NMD) 정도이다(2는 가로, 세로). 그러니 그냥 어렵게 DP같은걸 끼얹을 필요 없이 그냥 브루트포스를 활용한 구현문제로 보면 된다. 가로, 세로 좌표 [0~N-D, 0~M-D] 의 모든 지점에 대해서 그 우측으로 D번동안 장애물이 없다면 성공, 마찬가지로 아래쪽으로 D번 동안 장애물이 없다면 성공으로 치면 된다. 이하 그림에서는 N=3, M=3, D=2 인 경우 나올 수 있는 모든 경우를 그려보았고 그 중 장애물에 걸리지 않은 경우를 노란색, 걸린 경우를 회색으로 나타냈다. 이걸 코드로 구현만 하면 된다! 코드 : github import java.io.BufferedReader; import ja.. 2022. 3. 11.
백준 14719 자바 - 빗물 (BOJ 14719 JAVA) 문제 : boj14719 '문제'에 나온 이미지를 다시 그려봤다. 이 때 물이 차는 높이를 어떻게 알 수 있을까? 우선 3D로 생각해서 좌측에서 블록들을 본다고 생각해보자. 이 때 물은 좌측에서 시선에 닿는 만큼 차오를 수 있다. 즉 좌측에서 봤을 때 눈에 보이는 부분들에 들어찰 것이다. 좌측에서만 보면 아래와 같이 생각할 수 있다. 이 때 우측은 당연히 저렇게 들어차면 안된다. 따라서 우측에서도 확인해야 한다. 이번엔 우측에서 한번 봐본다고 생각해보자. 그럼 이렇게 생각될 수 있다. 그럼 이제 좌측에서 본 것과, 우측에서 본 것을 합쳐서 각 블록마다 좌측에서 봤을때와 우측에서 봤을 때 보였던 높이 중 작은 쪽을 선택하면 아래와 같이 된다. 좀 더 구체적으로 정의하자면 다음과 같다. 좌측부터 w방향으로 .. 2022. 3. 10.
백준 21356 자바 - Hundraelva kronor (BOJ 21356 JAVA) 문제 : boj21356 간단한 그리디 문제이다. 최소의 지폐 수를 구해야 하므로, 큰 값을 가지는 지폐부터 나누어나가면 된다. 문제의 제한에 맞는 1로 만들 수 있는 가장 큰 수부터 (111,111,111) n이 0이 될 때까지 한 자리씩 줄여나가면서(111,111,111 -> 11,111,111 -> 1,111,111 -> ... -> 1) 나눈 몫이 결국 출력해야 하는 지폐의 수이다. 그리고 매번 남은 나머지가 남은 지폐의 양이 된다. 결국 최종적으로는 1로 나누게 되므로 답을 못구하는 경우는 없다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private void so.. 2022. 3. 9.
백준 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.

티스토리툴바