반응형 Problem Solving155 백준 1826 : 연료 채우기 https://www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net [ 문제풀이 ] 주유소를 사용하는 비용이 모두 동일하기 때문에 더 이상 이동할 수 없는 경우 현재 이동한 거리 내의 주유소 중 최대 연료의 양을 가지는 주유소를 선택하는 것이 최선의 선택이다. 따라서 주유소를 연료의 양을 기준으로 우선순위 큐에 저장해놓으면서 더 이상 이동할 수 없을 경우 이동할 수 있는 연료의 양을 만들어주면 된다. 연료를 만드는 도중 우선순.. 2021. 8. 26. 백준 13308 : 주유소 https://www.acmicpc.net/problem/13308 13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도 www.acmicpc.net [ 문제풀이 ] 다익스트라 + dp를 활용해서 해결할 수 있는 문제이다. 최소 비용을 가지기 위해서는 다른 정점으로 이동할 때 현재까지 방문한 주유소 중 가장 싼 주유소만을 사용해야 한다. 이를 위해 현재까지 방문한 주유소 중 가장 싼 비용을 저장하여 관리해준다. 또한, 예시처럼 방문한 정점을 다시 방문하는 경우가 생길 수 있기 때문에 dp 테이블을 하나 선언하여 중복 방.. 2021. 8. 25. 백준 15678 : 연세워터파크 https://www.acmicpc.net/problem/15678 15678번: 연세워터파크 첫 줄에 징검다리의 수 N과 문제에서 설명한 D가 주어진다. (2 ≤ N ≤ 105, 1 ≤ D ≤ N-1) 이어 N개의 정수로, 각 징검다리에 쓰인 수 Ki가 1번 징검다리부터 N번 징검다리까지 순서대로 주어진다. (-109 www.acmicpc.net [ 문제풀이 ] 11003 최솟값 찾기 문제랑 거의 비슷한 문제이다. 좌측에서 우측으로 탐색하면서 구간 내의 최댓값을 유지해주면 되는 문제이기 때문에 덱(Deque) 자료구조를 활용해서 항상 덱에 구간 내의 첫 번째, 두 번째 최댓값을 유지해준다. import java.io.BufferedReader; import java.io.BufferedWriter; i.. 2021. 8. 24. 백준 9328 : 열쇠 https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net [ 문제풀이 ] bfs + set을 활용하면 해결할 수 있는 문제이다. Key의 종류가 최대 26개이기 때문에 이를 비트로 표현하려면 2^26(67108864)만큼의 공간이 필요하다. 이는 쓸데없는 메모리를 많이 사용하기 때문에 set을 이용해서 관리해주도록 하자. 또한, 시작점을 어디부터 시작하느냐에 따라서 얻을 수 있는 문서의 개수가 달라지기 때문에 한 번의 탐색으로 처리할 수는 없다. 따라서 아직 발견하.. 2021. 8. 23. 백준 1600 : 말이 되고픈 원숭이 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net [ 문제풀이 ] 일반적인 bfs + dp 문제에서 말로 움직일 수 있는 방법만 추가된 문제이다. 3차원 배열을 하나 선언해서 말의 방향으로 움직인 횟수에 따라 방문 표시를 해주면 된다. 가로길이가 W이고 세로길이가 H인 것만 주의하자. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.Input.. 2021. 8. 22. 백준 2021 : 최소 환승 경로 https://www.acmicpc.net/problem/2021 2021번: 최소 환승 경로 첫째 줄에 역의 개수 N(1≤N≤100,000), 노선의 개수 L(1≤L≤100,000)이 주어진다. 다음 L개의 줄에는 각 노선이 지나는 역이 순서대로 주어지며 각 줄의 마지막에는 -1이 주어진다. 마지막 줄에는 출발 www.acmicpc.net [ 문제풀이 ] 단순 BFS 문제인 줄 알았는데 생각보다 많이 애를 먹은 문제이다. 10번의 시도만에 겨우 성공하였다... 이 문제를 풀기 위해선 노선을 정점으로 두는 것이 아닌 노선이 속하는 경로를 정점으로 두는 아이디어가 중요한 것 같다. 단순히 노선을 정점으로 BFS를 한다면 경로를 선택하는데 있어서 방문 표시로 인해 문제가 발생하게 된다. 따라서 노선이 속하는.. 2021. 8. 21. 백준 11003 : 최솟값 찾기 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net [ 문제풀이 ] 처음에는 세그먼트 트리를 사용하였는데 TLE가 발생하였다. 이 문제는 덱(Deque) 자료구조를 활용하면 해결할 수 있는 문제이다. 1부터 N까지 순차적으로 탐색하면서 덱을 항상 L개 이하의 크기를 유지하면서 제일 첫 번째 원소는 범위에서 가장 작은 값을 가지도록 구현해주면 된다. import java.io.BufferedReader; import .. 2021. 8. 20. 백준 1956 : 운동 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net [ 문제풀이 ] 모든 정점에서 모든 정점으로의 최소 경로를 구할 수 있는 플로이드 와샬 알고리즘을 사용하면 쉽게 해결할 수 있다. dist[i][i]의 값이 INF가 아니라는 것은 자신에게 돌아올 수 있다는 것이기 때문에 i번 정점에서 출발하여 i번 정점으로 돌아오는 사이클 경로가 있다는 것을 의미한다. import java.io.BufferedReader; im.. 2021. 8. 19. 백준 1248 : 맞춰봐 https://www.acmicpc.net/problem/1248 1248번: 맞춰봐 규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느 날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 수도 www.acmicpc.net [ 문제풀이 ] 백트래킹 기반의 완전 탐색으로 해결할 수 있는 문제이다. 처음에는 중복 숫자가 허용되지 않는다는 조건이 없어서 21^10의 경우의 수가 존재하니 완전 탐색으로 불가능하다고 생각하였다. 그런데 아무리 고민해봐도 완전 탐색이 아니고서는 해결할 수 없을 것 같아서 가능성 없는 경우들을 걸러내어 최대한 경우의 수를 줄여나가도록 구현하니깐 통과하였다. import java.io.Buffe.. 2021. 8. 18. 이전 1 2 3 4 5 ··· 18 다음 반응형
