박카스러버

https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 해당 문제를 DP를 이용하여 문제를 해결하였습니다. 1차원 DP를 이용하게 되면 중복이 발생하여 2차원 DP를 이용하였습니다. 저는 dp[표현하고자 하는 숫자][계산 중 최대로 작은 숫자]를 이용해 문제를 해결하였습니다. dp[i][1] = dp[i-1][1]; dp[i][2] = dp[i-2][1] + dp[i-2][2]; dp[i]..

https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 저는 해당 문제를 DP를 이용하여 문제를 해결하였습니다. DP를 통해 해당 일자까지 오는데 최대 금액을 저장하도록 하였습니다. package BOJ.DP; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokeni..

https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 해당 문제는 LCA알고리즘을 이용하여 문제를 해결하였습니다. LCA알고리즘을 사용하려면 먼저 노드들을 depth와 parent로 표시해야합니다. LCA 로직은 다음과 같습니다. 1. 깊이가 더 깊은 노드를 더 낮은 노드까지 올려줍니다. 2. 두 정점의 깊이가 같아졌으면 각각의 노드가 같은지 확인하고 같다면 해당 노드를 출력하고 다르면 조상을 올려다보며 조상이 같아질 때까지 노드를 타고 올라간..

https://www.acmicpc.net/problem/3187 3187번: 양치기 꿍 입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다. 다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다. www.acmicpc.net 저는 해당 문제를 dfs를 이용하여 문제를 해결하였습니다. 벽을 제외한 곳에 dfs를 하고 이를 통해 해당 영역에 양과 늑대의 수를 카운팅하였습니다. dfs 결과값을 통해 늑대가 양보다 같거나 많으면 양을 0으로 양이 더 크다면 늑대를 0으로 만들고 최종 결과값에 이를 반영하여 문제해결하였습니다. package BOJ.DFS; import java.io.BufferedReader; i..

https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net 저는 해당 문제를 BFS를 적용시켜 문제를 해결하였습니다. 각각의 1을 Queue에 넣어서 BFS를 진행하였고, 전체 맵을 다 방문하는데 얼마나 걸리는지를 확인하여 이를 결과값으로 출력하였습니다. package BOJ.BFS; import java.io.BufferedReader; import java.io.InputStreamReader; import java.uti..

https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 저는 해당 문제를 DFS를 통해서 문제를 해결하였습니다. DFS를 통해 해당 연결된 개수가 몇개인지를 확인하고 이를 제곱하여 각각의 결과값에 더해주었습니다. package BOJ.DFS; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.function.Function; pub..

https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net BFS를 통해 문제를 해결하였습니다. 방문 체크는 visited[y좌표][x좌표][벽을 뿌순 개수]를 통해 하였습니다. BFS의 각각의 Node는 좌표와 벽을 몇개 뿌셨는지를 가지고 있습니다. package BOJ.BFS; import java.io.BufferedReader; import java.io.InputStreamReader; import java.u..

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 처음에는 단순 BFS로 문제를 해결하려 하였지만, 계속 메모리초과로 BFS로는 해결하지 못하였습니다. 그 다음으로는 다익스트라 방법을 응용하였습니다. 다익스트라는 한 점에서 다른 점까지의 최단 거리를 구하는 것이기 때문에 이를 활용하여 문제를 해결하였습니다. 저는 최단거리 대신 중량의 최대 값을 구하습니다. 시작점에서 방문하지 않은 가장 ..

https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 저는 해당 문제를 브루트 포스를 통해서 문제를 해결하였습니다. 기본적으로 5개는 알아야하기 때문에 k가 5보다 작다면 0을 바로 출력하였습니다. 먼저 조합으로 필수 5개를 제외한 k-5개의 알파벳을 뽑고 각각의 문자열이 뽑지 않은 문자열이 있는지 확인하고 그렇지 않다면 결과값을 하나 올려주어 해당 문제를 해결하였습니다. package BOJ.Bruteforce; import java.io...

https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 저는 해당 문제를 수열의 합 공식을 통해 해결하였습니다. 합이 주어지고 서로 다른 N개의 자연수의 합이 이와 같아야 되기 때문에 저는 제일 작은 1부터 차근차근 더해가면서 늘리는 것을 생각하였습니다. 그리고 1부터 N까지의 합이 주어진 S와 같다면 좋겠지만, 이와 다를 수 있습니다. 만약 1~N까지으로 이를 표현하지 못한다면, 1~N까지의 합이 S를 넘는 바로 N값에서 1을 뺏습니다. 이유는 1~ n-1의 합에서 S의 나머지 값을 n-1에 더해주면 된다고 생각을 하였습니다. 여기서 1~n의 합이 S보다 작기 때문에..