본문 바로가기

PS834

백준 3164 자바 - 패턴 (BOJ 3164 JAVA) 문제 : boj3164 우선 뭐 배열에 직접 그린 후에 직접 세는 방식은 O(X*Y) = O(10^12) 이므로 불가하다. 애초에 메모리도 엄청 많이 들 것이다. X와 Y가 최대 10^6 이므로 시간내에 풀기 위해서는 O(N)이나 O(NlogN) 급의 풀이가 필요하다. 혹시 어떻게 푸는지 감이 안왔다면 아래의 그림을 보면 바로 아! 라고 외칠 것이다. 그래프를 2개로 나눠서 보면 쉽게 풀이법을 생각해낼 수 있다. 문제에서 제시된 그래프 그대로 풀이를 찾기엔 좀 난해할 수 있지만, 아래와 같이 가로 성분과 세로 성분을 나눠서 생각해보면(세로 성분의 맨 위는 가로성분에 이미 포함된다.) 그냥 범위내에 포함되는 매번 +2씩 증가하는 기둥의 길이를 구하는 문제가 된다. 가로 기둥 최대 50만개, 세로 기둥 최대.. 2022. 3. 19.
백준 17162 자바 - 가희의 수열놀이 (Small) (BOJ 17162 JAVA) 문제 : boj17162 mod가 최대 10^2라서 뭐 복잡한 알고리즘 필요없이 풀 수 있다. 결국 나누었을 때 0, ..., mod-1인 수가 어느 idx 위치에 있냐가 중요하다. 이걸 빨리 알 수 있으면 되는건데, mod가 10^2이니깐 대충 O(Q * mod) 정도의 시간복잡도만 가져도 풀 수 있다. 그럼 해볼만한게 많이 있다. 내 경우엔 어차피 맨 뒤에서만 수가 추가되고 빠지니 스택을 사용했다. 그리고 mod개 만큼의 스택을 마련했다. 스택배열을 arr이라고 하고, 현재 넣을 위치를 idx라고 하겠다. 그럼 각 쿼리에 대해 다음과 같이 대응할 수 있다. --- [ 쿼리 : 1 num ] arr[num % mod]에 num을 추가하고 idx++ -> O(1) [ 쿼리 : 2 ] 최대 10^2개인 a.. 2022. 3. 18.
백준 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.

티스토리툴바