박카스러버

https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 저는 해당 문제를 DP를 이용하여 문제를 해결하였습니다. 처음에는 break를 사용하지 않아 시간이 2초가 살짝 넘었습니다. 돈을 5원짜리 먼저 그리고 for문도 제일 큰 값에서 줄여나가는 식으로 하여 가장 먼저 값을 찾을 때가 제일 동전의 개수가 적기 때문에 INF가 아니면 바로 break를 해 1초 안에 돌아가도록 하였습니다. package BOJ.DP; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.functio..

https://www.acmicpc.net/problem/14465 14465번: 소가 길을 건너간 이유 5 첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다. www.acmicpc.net 저는 슬라이딩 윈도우 개념을 이용해 문제를 해결하였습니다. boolean배열을 통해 에러 지점을 확인하고 for문으로 true면 cnt값을 늘리고 i-k이 true면 cnt값을 줄이면서 result와 cnt를 비교해 문제를 해결하였습니다. package BOJ.TwoPoint; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import j..

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 저는 해당 문제를 우선순위 큐 2개와 map이용해 문제를 해결하였습니다. map을 이용해 지금 어떤 숫자가 몇개 있는지를 체크하였습니다. 우선순위 큐는 한개는 오름차순 하나는 내림차순으로 하여 꺼낼 때마다 map에서 해당 숫자가 존재하는지를 체크하고 없다면 계속 뽑도록 하였습니다. 저는 우선순위 큐를 초기화할 때 실수를 하여 오래걸렸습니다. PriorityQueue maxQ = new Prio..

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 저는 해당 문제를 우선순위 큐를 이용해 문제를 해결하였습니다. 우선 순위 큐를 통해 작은 값 두개를 꺼내서 더해주고 이 값을 result에 더하고 다시 큐에 넣었습니다. 위의 과정을 큐의 사이즈가 1이 될때까지 하였습니다. package BOJ.ETC; import java.io.BufferedReader; import java.io.InputStreamReader; import j..

https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 저는 해당 문제를 이분탐색과 BFS를 이용해 문제를 해결하였습니다. 저는 이분탐색을 통해 차이값을 찾고 이를 BFS를 통해 해당하는지를 확인하였습니다. 처음에는 이분탐색과 DFS를 통해 문제를 해결하려 하였지만, 시간초과가 나왔습니다. 아마 백트래킹으로 인해 중복으로 들어가는 노드들이 있어 그런거 같습니다. package BOJ.DFS; import java.io.Buffe..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 저는 해당 문제를 BFS를 이용해 문제를 해결하였습니다. BFS를 통해 1(익은 토마토)를 4방탐색하여 0(안익은 토마토)가 존재하면 q에 넣고 1로 변경해줍니다. q에 아무것도 없는데 안 익은 토마토가 존재하면 모두 익지는 못하는 상황이므로 -1을 리턴합니다. 그것이 아니라면 토마토가 다 익은 시점의 time을 리턴합니다. package BOJ.BFS; import java.io..

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 저는 해당 문제를 DFS를 활용해 해결하였습니다. DFS를 이용해 0인 곳에서 사용할 수 있는 값들을 확인하고 (prunning) 이 값들을 넣어보면서 진행하였습니다. 처음에 다시 0 으로 되돌리는 코드가 없어서 계속 제대로 된 값이 되지 않았습니다. DFS라면 백트래킹을 하기 때문에 원본으로 되돌리는 코드가 있어야합니다. 그리고 0인 곳에 1 ~ 9까지 값을 대입하고 해당 값이 유효한 지를..

https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 저는 해당 문제를 스택 개념을 조금 활용하여 문제를 해결하였습니다. 저는 스택 대신 이전에 '('가 몇개 있었는지를 확인하였습니다. 그리고 ')'가 나온다면 (의 개수를 줄이고 결과값에 더해주었습니다. 하지만 바로 이전에 ')'가 나오고 ')'가 또 나온다면 이때는 막대기의 끝부분이기 때문에 결과값에 1만 늘렸습니다. package BOJ.ETC; import java.io.BufferedReader; im..

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 저는 해당 문제를 BFS를 이용해 문제를 해결하였습니다. 저는 0의 영역을 나누고 넘버링을 하여 해당 영역에 0이 몇개 있는지를 판단하였습니다. 다음으로 1에 대해 근처 0의 영역의 개수를 더해줌으로써 문제를 해결하였습니다. 만약 왼쪽과 아래가 같은 영역을 수 있기 때문에 Set을 통해 해당 영역의 개수를 더해주었는지 확인하였습니다. package BOJ.DFS; import..

https://www.acmicpc.net/problem/2792 2792번: 보석 상자 보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하 www.acmicpc.net 저는 해당 문제를 이분탐색으로 해결하였습니다. 이분탐색으로 mid값이 질투심을 만족하는지를 확인하였습니다. 보석의 개수를 mid값으로 나눠 이 값이 n보다 작은지를 확인하여 작다면 max 값을 줄여주고 , 크다면 min값을 늘리면서 최대 질투심을 구하였습니다. package BOJ.BinarySearch; import java.io.BufferedReader; import java.io.InputS..