박카스러버

https://www.acmicpc.net/problem/1337 1337번: 올바른 배열 첫째 줄에 배열의 크기 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 배열의 원소가 한 줄에 하나씩 주어진다. 원소는 1,000,000,000보다 작거나 같은 음이 아닌 정수이 www.acmicpc.net 저는 투포인트를 이용해 문제를 해결하였습니다. 입력 배열을 오름차순 정렬하였습니다. 시작 포인트와 끝 포인트의 값의 차가 5미만이라면 끝포인트를 늘리면서 결과값을 작은 값으로 초기화시켰습니다. 반대로 5이상이라면 시작 포인트를 늘려주었습니다. package BOJ.twopoint; import java.io.BufferedReader; import java.io.InputStre..

https://www.acmicpc.net/problem/21938 21938번: 영상처리 화면의 세로 $N$, 가로 $M$ 값이 공백으로 구분되어 주어진다. 두 번째 줄부터 $N + 1$줄까지 $i$번째 가로를 구성하고 있는 픽셀의 $R_{i,j}$, $G_{i,j}$, $B_{i,j}$의 값이 공백으로 구분되어 총 $M$개 주어진 www.acmicpc.net 저는 BFS를 통해 해당 문제를 해결하였습니다. 저는 makeMap 함수를 통해 평균이 경계값보다 큰지를 판단하여 높다면 새로운 배열에 255값을 넣었습니다. 새로운 배열에서 방문하지 않은 노드를 돌면서 255값이라면 BFS를 통해 인접한 노드들을 방문체크하여 다시 방문하지 않도록 하여 물체의 개수를 구하였습니다. package BOJ.bfs; ..

https://www.acmicpc.net/problem/11123 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net 저는 해당 문제를 BFS를 통해 해결하였습니다. 방문하지 않은 곳에 BFS를 하여 방문 체크를 하면서 무리의 개수를 확인하였습니다. package BOJ.bfs; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; imp..

https://www.acmicpc.net/problem/21937 21937번: 작업 민상이가 작업할 개수 $N$와 작업 순서 정보의 개수 $M$이 공백으로 구분되어 주어진다. 두 번째줄부터 $M + 1$ 줄까지 작업 $A_i$와 작업 $B_i$가 공백으로 구분되어 주어진다. 이때 두 값의 의미는 작 www.acmicpc.net 저는 BFS를 통해 문제를 해결하였습니다. BFS를 통해 저는 끝내야 하는 작업에서 시작해서 BFS를 진행하여 몇개의 노드를 방문하는지를 체크하여 결과를 찾았습니다. package BOJ.bfs; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import j..

https://www.acmicpc.net/problem/24463 24463번: 미로 첫 번째 줄에는 미로의 크기 $N, M$이 주어진다. $(3 \le N, M \le 2,001$, $N, M$은 홀수$)$ 두 번째 줄부터는 미로의 정보가 주어진다. 두 번째 줄부터 $N$줄에 거쳐 각 줄에는 길이가 $M$이고 .과 +만으로 이 www.acmicpc.net 저는 BFS와 DFS를 통해 문제를 해결하였습니다. BFS를 통해 시작점에서 끝점까지의 최단 경로를 구하고 dir에 해당 좌표에 최단 거리로 어떤 방향으로 왔는지의 역순으로 저장하였습니다. 마지막으로 끝점부터 시작해 dir에 저장한 방향대로 시작점까지 가는 경로를 '.'으로 표현하였습니다. 혹시 2 또는 4%에서 시간초과가 나오신다면, 마지막에 경로..

https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 저는 해당 문제를 DP를 이용하여 해결하였습니다. 저는 마지막 색을 구하고 나머지는 앞의 색과 다르게 선택하고, 마지막에서 2번째는 앞과 맨 뒤에 선택한 것을 선택하지 않도록 하였습니다. DP를 통해 이전에 계산한 것을 다시 계산하지 않도록 하였습니다. package BOJ.dp; import java.io.BufferedReader; import java.io.Inp..

https://www.acmicpc.net/problem/10025 10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.acmicpc.net 저는 투포인트를 이용해 문제를 해결하였습니다. 투포인트를 통해 범위의 가중치 합을 구하여 최대를 찾았습니다. package BOJ.twopoint; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import j..

https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 저는 LIS를 이용하여 문제를 해결하였습니다. LIS를 이용하여 최장 증가 부분 수열을 구하고 이를 전체 길이에서 빼 문제를 해결하였습니다. package BOJ.dp; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer..

https://www.acmicpc.net/problem/22233 22233번: 가희와 키워드 1번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, floyd, os가 됩니다. 2번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, os가 됩니다. map은 1번째 글과 2번째 글에 중복으로 등장하였음을 www.acmicpc.net 저는 구현을 통해 문제를 해결하였습니다. Set을 통해 이전에 나온 키워드를 저장하고 블로그에 작성하면 키워드를 set에서 지우도록 하였습니다. package BOJ.bfs; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashSet; import java.uti..

https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 저는 슬라이딩 윈도우를 통해 문제를 해결하였습니다. 슬라이딩 윈도우를 통해 x의 간격의 각각 합을 구하고 각각의 합을 비교해 이때 최대를 구하고 개수를 구하였습니다. package BOJ.twopoint; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; impor..