본문 바로가기

PS/BOJ764

백준 2602 자바 - 돌다리 건너기 (BOJ 2602 JAVA) 문제 : boj2602 이게 돌다리 2개를 번갈아 건너는 부분을 어떻게 처리할지 감이 잘 안올 수 있어서 그렇지, 그 부분 때고 생각하면 생각보다 어렵지 않다. 1. 그러니 우선 돌다리가 한 줄만 있다고 치고 생각해보자. 이 경우에도 모든 경우를 보기에는 당연히 무리가 있다. 대강 100! (팩토리얼) 정도 나올테니 다 볼순 없다. 브루트포스로 하진 못하겠고, 그럼 돌다리 한 줄만 우선 본다고 했으니 "RRGGSR"에서 "RGS"를 건너면서 지나가는 경우를 생각해보자. 이런건 DP를 사용해 구하면 효율 좋게 구할 수 있다. dp[a][b]를 "RGS"에서 a 인덱스 까지를 표현하는 가지수, b는 "RRGGSR"의 인덱스 라고 정의해보자. 이 경우 다음과 같이 그려볼 수 있다. 최종적으로 가장 우측 아래에.. 2022. 3. 18.
백준 11637 자바 - 인기 투표 (BOJ 11637 JAVA) 문제 : boj11637 우선 직관적으로 생각하기엔 아주 간단하다. 각 테스트 케이스에 대해 n명의 득표 수 합계(이하 sum)를 구하고, 그 n명 중 가장 큰 값(이하 max)을 기준으로 다음과 같이 나뉜다. 1. max값을 가졌던 인원이 2명 이상인 경우 : no winner 2. sum/2+1 0) { int n = nextInt(); int max = 0; int maxIdx = -1; int sum = 0; int idx = 0; boolean chk = true; while (idx++ 2022. 3. 17.
백준 5568 자바 - 카드 놓기 (BOJ 5568 JAVA) 문제 : boj5568 우선 항상 문제를 풀 때, 그냥 무지성으로 모든 경우를 봐도 주어진 시간, 메모리 내에 가능한지부터 확인하는 습관을 들이는게 좋다. 이 문제의 경우엔 최대 10개 중 최대 4장을 선택하면 되므로, 최대 10C4번만 보면 된다. 따라서 그냥 모든 경우를 보면 된다! -> 모든 경우를 확인하려면 k번의 반복문이 필요하다. 이렇게 반복문의 개수가 고정되지 않을 때는 재귀로 짜면 매우 편하다. 재귀를 쓰기 싫다면 스택을 쓰면 재귀로 짠 것과 동일하게 짤 수 있다. 그럼 '만들 수 있는 정수'의 종류는 어떻게 알 수 있을까? 마찬가지로 제한 조건을 확인해보면서 생각해보면 된다. 우선 1부터 99까지의 정수이므로 0이 없어서, 숫자 앞에 0이 오는 경우는 무시해도 됨을 알 수 있다. 그리고 .. 2022. 3. 16.
백준 18258 자바 - 큐 2 (BOJ 18258 JAVA) 문제 : boj18258 문제에 제시된 대로 구현만 잘 하면 되는 문제이다. 큐를 직접 구현해봐도 되고, 자바 혹은 다른 언어에서 제공하는 기본 큐를 사용해서 짜도 된다. '만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.' 와 같은 세세한 조건들만 잘 처리해주면 쉽게 통과할 수 있다. 코드 : github import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.LinkedList; import java.util.PriorityQueue; .. 2022. 3. 15.
백준 3022 자바 - PRASE (BOJ 3022 JAVA) 문제 : boj3022 반복 로직만 잘 세우면 간단하게 풀 수 있다. 주의할 부분은 'If at any point a child takes a piece of food, and that child had already taken more food than the other children all together (not including the new piece of food),'에서 not including the new piece of food 부분이다. 즉, 현재 아이가 누군지는 알아야하지만 현재 집은것에 대해서는 카운티앟지 않은채로 수만 확인해야 한다. 따라서 현재까지 나온 아이의 총 수를 cnt, 현재 아이가 나왔던 횟수를 cc[아이이름] 이라고 해보자. 그럼 만약 현재 아이의 이름이 A라고 할.. 2022. 3. 14.
백준 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.

티스토리툴바