박카스러버

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 해당 문제는 그래프의 순서가 존재하여 위상정렬을 사용하여 문제를 풀었습니다. 저는 각각의 노드에 들어오는 최대 시간을 구하였습니다. 각각의 노드에서 다른 노드로 갈 때 시간들을 구했고, 이를 time이라는 배열에 넣어서 관리하였습니다. 이 중 최대 값을 구하여 문제를 해결하였습니다. package BOJ.Graph; import java.io.BufferedReader; import java..

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 저는 DP를 적용하여 문제를 해결하였습니다. 0번째 인덱스는 해당 라인에 사자를 넣지 않는 것으로 설정하였습니다. 해당 라인에 아무것도 없다면 이전 인덱스의 1,2 둘 다 가능하기 때문에 dp[n][0] = dp[n-1][0] + dp[n-1][1] + dp[n-1][2] 으로 점화식을 만들었습니다. 해당 라인에 왼쪽 (1)에 사자를 넣으면 이전 인덱스에서 2만 넣을 수 있기 때문에 점화식 dp[n][1] = dp[n-1][0] + dp[n-1][2] 으로 만들었습니다. 오른쪽(2) 도 위와 같은 방식으로 점화식을 만들면 dp[n..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 이번 문제는 예외처리를 제대로 하지 않아서 계속 틀렸습니다. 첫번째 예외처리를 하지 않은 것은 0의 길이에 대한 예외처리를 하지 않았습니다. (13%정도에서 틀렸습니다.) 두번째 예외처리를 하지 않은 것은 m이 0일때 입력을 받았던 것이였습니다. (83%정도에서 null pointer) package BOJ; import java.io.BufferedReader; import ja..

https://www.acmicpc.net/problem/14716 14716번: 현수막 혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라. www.acmicpc.net 저는 visited배열을 통해 각 지점에 대한 방문체크를 하였습니다. 또한, dfs를 통해 계속 재귀적으로 들어가도록 구현하였습니다 package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.function.Function; public class BOJ_14716 { static int n,m; static int map[][]..

https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 해당 문제는 슬라이딩 윈도우를 통해서 해결하였습니다. 저는 해당 문제를 풀면서 2가지를 간과하였습니다. 1. i >= k일때 결과값 초기화 2. 결과값을 0으로 초기화 1번 같은 경우 n == k일 경우 결과값이 안나오게 됩니다. 이래서 i >= k-1일때부터 결과값을 초기화해야합니다. 무작정 계속 초기화하게 되면 k일보다 작은 경우도 들어가기 때문에 안됩니다. 2번 같은경우 현재 문..

https://www.algospot.com/judge/problem/read/BOARDCOVER algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 www.algospot.com 처음에는 블록을 맨 위 맨 왼쪽으로 설정하지 않아 결과값이 제대로 나오지 않았습니다. 이렇게 되면 중복된 값이 나오거나 값이 제대로 나오지 않을 수 있습니다. package Algospot; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util...

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net TSP문제 + DP문제입니다. TSP만 사용하면 시간초과가 나오는 문제입니다. 저는 처음에 DP를 비트마스킹해서 경로로만 해서 문제를 계속 틀렸습니다. 이때의 문제점은 해당 루트의 끝 즉, 현재 위치가 어디든 같은 DP값으로 본다는 것이였습니다. 그래서 현재 어디 점이 있는지 까지를 DP로 넣어서 문제를 해결하였습니다. package BOJ; import ja..

https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 저는 중복제거를 위해 DP를 이용해 접근하였습니다. 또한 입력의 세번째 인자 값을 확인하여 배열에 순차적으로 넣지 않고 수학적으로 접근하여 행과 열을 구하였습니다. package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer..

https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 저는 해당 문제를 위상정렬을 이용하였습니다. count배열을 통해 해당 노드가 사이클에 있는지 확인하였습니다. 사이클을 먼저 확인하고 사이클에서 각각의 노드에 dfs를 사용해 사이클과의 거리를 확인하였습니다. package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.u..

https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 입력을 받고 스택의 peek 값이 해당 입력값보다 작으면 해당 숫자까지 스택에 넣어주고, 해당 숫자를 pop합니다. 만약 스택이 비어있거나 peek값이 해당 숫자와 같지 않다면 해당 수열을 만들수 없기 때문에 flag를 false로 만들었습니다. package BOJ; import java.io.BufferedRea..