문제풀이/백준
-
[백준]14502: 연구소 - JAVA문제풀이/백준 2021. 2. 21. 17:41
[백준]14502: 연구소 www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 조합 + 탐색문제이다. 조합을 사용하는 이유는 벽의 위치를 뽑을 때 순서가 상관없기 때문에 조합을 사용했다. 조합을 구현할 때 다음에 뽑을 벽의 위치를 부분이 까다로웠다. 이전의 뽑은 벽의 위치보다 이후의 위치에서 벽을 선택해야 했는데 입력받은 node는 이차원 배열로 되어있어 y값을 어떻게 처리해야 할지 고민이 되었다. 처음에는 다음과 같이 구현하였다. for(int i = x; i < n..
-
[백준]1937: 욕심쟁이 판다 -JAVA문제풀이/백준 2021. 2. 21. 15:02
[백준]1937: 욕심쟁이 판다 www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 풀이 처음에는 DFS만 사용해서 풀었더니 시간초과가 났다! DP와 DFS를사용해 메모이제이션 하면서 풀어야 한다. dp에 저장되는 값은 다른 위치에서 현재 위치까지 이동할 수 있는 거리 중 최대값을 의미한다. 그러므로 이동하면서 계속 갱신해 주어야 한다. 즉 현재위치가 x, y이고 이동할 위치가 nx, ny라고 할 때 dp[x][y] = dp[nx][ny] + 1과 dp..
-
[백준]5052: 전화번호 목록 - JAVA문제풀이/백준 2021. 2. 20. 17:18
[백준]5052: 전화번호 목록 www.acmicpc.net/problem/5052 풀이 이 문제는 문자열 관련한 새로운 지식을 많이 쌓을 수 있었던 문제였다. 우선, 숫자를 String으로 입력받고 Arrays.sort()를 사용해 정렬을 하면 기존의 숫자 정렬과는 결과가 다르다. 기존의 숫자 정렬은 1, 9, 10, 44, 34, 4로 입력되었을때 정렬 결과가 1, 4, 9, 10, 34, 44가 된다. 그러나 이를 String으로 입력하고 정렬하면 결과가 1, 10, 34, 4, 44이 된다. 그 이유는 프로그램은 숫자가 아닌 문자로 인식해서 오름차순 정렬을 하기 때문이다. ( ex) 다 가나 다라 나 가 -> 가 가나 나 다 다라 순서로 정렬되듯이.) 이해가 잘 되는 예시는 다음과 같다. 입력) ..
-
[백준]1520: 내리막 길 - JAVA문제풀이/백준 2021. 2. 19. 21:34
[백준]1520: 내리막 길 www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 풀이 DP문제로 dfs 풀이 방식과 매우 유사한 형식이였다. 그래서 많이 어렵지 않았다. node함수로 지도의 정보를 입력받고, dp함수를 사용해 메모이제이션과 현재 까지 올 수 있는 경로의 수를 저장해 주었다. dp함수가 초기값이면 그 방향으로 한번도 오지 않았다는 의미이므로 지도 값이 더 작은 곳이 주변에 위치하는지 확인하여 이동한다. 이때 이동 경로의 수를 더해준다. dp함수..
-
[백준]2170: 선 긋기 - JAVA문제풀이/백준 2021. 2. 18. 16:18
[백준]2170: 선 긋기 www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 풀이 선의 정보를 입력 받은 후 계산을 순차적으로 진행하기 위해 x좌표를 기준으로 오름차순 정렬을 한다. x좌표가 같으면 y 좌표를 기준으로 오름차순 정렬 한다. 이전 선의 정보를 min, max에 저장해 주었고 현재 선의 정보와 비교하면서 조건에 따라 길이를 계산해 주었다. 선의 길이를 계산할 때 다음과 같은 3가지 조건이 있다.(이때 모든 선은 x, y..
-
[백준]2341: DDR - JAVA문제풀이/백준 2021. 2. 18. 13:34
[백준]2341: DDR www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 풀이 DP문제로 왼쪽, 오른쪽 발의 위치를 바꾸어 가면서 최소값을 찾아내야 한다. 이때 항상 이전의 왼쪽 발의 위치와 오른쪽 발의 위치를 기억하고 있어야 해서 DP를 3차원 배열로 선언해 주었다. DP[][][]에서 각 자리의 의미는 DP[현재 밟아야 할 위치][이전의 왼쪽발 위치][이전의 오른쪽발 위치]이다. 이러한 상황에서 두 가지 경우가 존재한다...
-
[백준]1238: 파티 - JAVA문제풀이/백준 2021. 2. 17. 17:44
[백준]1238: 파티 www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 처음에는 다익스트라 알고리즘을 사용하여 풀려고 하였다. X에서 모든 마을 까지의 거리를 구하는 방법은 어렵지 않았으나 모든 마을에서 X까지 거리를 구하는 방법이 어려웠다. 결국 각각의 마을에서 X까지 가는 모든 최단거리를 구하고 그 중에 X로 가는 거리만 뽑아내려고 하였다. 그런데 생각해보니 이건 모든 노드에서 모든 노드까지의 최단거리를 구하는 것과 다..
-
[백준]11404: 플로이드 - JAVA문제풀이/백준 2021. 2. 17. 15:11
[백준]11404: 플로이드 www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 최단거리 알고리즘 공부한 기념으로 관련 문제들을 풀어보았다. 이 문제는 플로이드-워샬 알고리즘을 쓰면 바로 답이 나온다! 모든 정점에서 모든 정점까지의 최단거리를 구하는 문제이다. 문제를 꼭 제대로 읽자! 출력 설명에 i에서 j로 가는 길이 없으면 0을 출력한다고 되어있다. 이를 체크 안해주면 98프로에서 틀린다. 꼭꼭 문제를 제대로 읽자. 코드 1 2 3 4 5 6 7 8 9..