https://www.acmicpc.net/problem/30024 30024번: 옥수수밭 옥수수밭 주인 민석이는 한 해 동안 열심히 기른 옥수수를 수확하려고 한다. 옥수수밭은 $N$행 $M$열의 격자로 생각할 수 있는데, 격자의 각 칸에는 한 그루의 옥수수가 심어져 있다. 민석이는 각 www.acmicpc.net 문제 조건 이 문제는 조건이 아주 단순해서 깊게 구현할 필요가 없었다. '현재 접근할 수 있는 옥수수 중 가장 가치가 높은 것'만 확인하면 된다. 이에 따라 제일 처음 2차원 map 배열을 받으면서 가장자리에 있는 옥수수들의 값을 우선순위 큐에 넣었다. PriorityQueue que = new PriorityQueue(new Comparator() { @Override public int c..
분류 전체보기
https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net Dijkstra 알고리즘과 Priority Queue 보통 다익스트라 알고리즘을 사용할 때 우선 순위 큐보다는 for문을 사용했는데, 이번 문제는 거리가 가장 작은 노드를 매번 찾으면 시간 초과가 났다. N의 최대 값이 100,000이기 때문에 for문으로 dist 배열을 돌리면서 거리가 가장 짧은 노드를 찾는다면 최대 10,000,000,000번 조사하게 된다. 하지만..
https://www.acmicpc.net/problem/21922 21922번: 학부 연구생 민상 첫 번째 줄에는 연구실의 크기가 세로 $N(1 \le N \le 2,000)$, 가로 $M(1 \le M \le 2,000)$ 순으로 주어진다. 두 번째 줄부터 $N + 1$ 줄까지 연구실 내부 구조 정보를 알려주는 값 $M$개가 주어진다. $1,2,3,4$ www.acmicpc.net 방향 바꾸는 조건 에어컨 바람이 사방으로 퍼져나가는 것이 아니라, 직선으로 움직이는 것을 먼저 알아야 한다. 가장 처음, 에어컨 위치에서만 사방으로 퍼지고 그 이후에는 (물건을 만나지 않는 이상) 한 방향으로 움직인다. 게다가 에어컨이 1개라는 보장은 없다. 예제 2처럼 에어컨이 2개 이상 나올 수 있기 때문에, 방 구조를..
https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 내가 걸린 예외사항들 문제 자체는 최단 거리를 위해 BFS를 계속 사용하기만 하면 되는데, 생각 못한 예외사항 때문에 계속 틀렸습니다 를 받았다. 1. 목적지가 중복될 수 있다. 입력의 제한 사항에는 "모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다."라고만 되어 있기 때문에 각 승객의 출발지는 달라도 목적지..
https://www.acmicpc.net/problem/1069 1069번: 집으로 은진이는 지금 (X, Y)에 있고, (0, 0)에 있는 집으로 가능한 빨리 가려고 한다. 이동할 수 있는 방법은 다음 두 가지이다. 첫 번째 방법은 걷는것이다. 걸을 때는 1초에 1만큼 움직인다. 두 번째 방법 www.acmicpc.net 문제 이해 지금껏 풀었던 대부분의 문제가 배열을 바탕으로 한 칸씩 이동하는 것이었기 때문에 처음 문제를 이해할 때 애를 먹었다. 이 문제에서 '1만큼 움직인다'는 1칸 움직이는 게 아니라 그냥 1 움직이는 것이다. 어느 방향이든 상관 없이. 빨리 가는 조건 가장 먼저 알아야 하는 것은 방향에 구애받지 않고 움직인다면, 거리가 D * 2 이하인 경우 점프 두 번으로 무조건 도달할 수 있..
https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net [백준] 11660번 : 구간 합 구하기 5 누적 합 구하기 배열을 전부 받은 후, map[i][j]에는 (0, 0)부터 (i, j)까지의 모든 합이 들어가도록 계산했다. 우선 각 행의 0부터 N까지 열을 누적하고, 모든 행을 완료한 후에는 열을 기준으로 각 행을 누적해주었다. 예를 들어 예제 1이라면 누적된 배열은 다음과 같다. (계산하기 쉽도록 0행과..
https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 가장 적은 방향 전환 제시된 조건에 따르면 아무리 멀리 돌아가더라도 방향 전환 횟수가 가장 적은 게 답이다. 따라서 방향 전환 횟수를 우선 순위로 두는 PriorityQueue를 사용하여 BFS를 돌렸다. BFS의 성질에 따라 가장 먼저 도착한 노드의 방향 전환 횟수가 정답이기 때문에 바로 break 해주었다. 방문 체크 가장 어려웠던 것은 방문 체크를 어떻게 해주느냐 였다. 한 번 방문..
https://www.acmicpc.net/problem/17484 17484번: 진우의 달 여행 (Small) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 다이나믹 프로그래밍 cost 배열에는 한 칸에 3개의 값을 저장하도록 했다. 오른쪽에서 왔을 때, 왼쪽에서 왔을 때, 그리고 직진했을 때의 연료 양의 합이다. 1. right : (i - 1, j + 1)에서 대각선으로 올 때 2. left : (i - 1, j - 1)에서 대각선으로 올 때 3. straight : (i - 1, j)에서 직진해서 올 때 연속으로 ..
