알고리즘 문제풀이

백준 9879번 - Cross Country Skiing 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1초 512MB 171 85 74 49.333% 문제 The cross-country skiing course at the winter Moolympics is described by an M x N grid of elevations (1 = M || nx >= N || visited[ny][nx] || abs(h[ny][nx] - h[y][x]) > D) continue; visited[ny][nx] = true; Q.push({ny, nx}); } } for (auto [y, x] : waypoints) { if (!visited[y][x]) return false; } return true..

백준 14658번 - 하늘에서 별똥별이 빗발친다 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2초 256MB 1490 467 380 32.285% 문제 “오빠! 나 얼마만큼 사랑해?” “널 위해서라면 저기 저 하늘의 별이라도 따다 줄 수 있어. 지금 따줄까?” “에이, 거짓말!” “정말이야. 한 번 봐봐!” 욱제는 하늘을 발로 차버렸다. 그랬더니 정말 별이 떨어졌다. 그런데, 정말로 별이 지구로 떨어지기 시작했다. 욱제는 지구를 지키는 정의의 용사가 되기로 결심했다. “자기야, 나 세계를 지키고 올게. 꼭 돌아올 테니 조금만 기다려줘.” 지구의 파괴를 막기 위해서는 지표면에 떨어지는 별똥별의 수를 최소화해야 한다. 욱제는 커다란 네모난 L*L 크기의 트램펄린을 준비했다. 별똥별이 어디로 떨어질지..

백준 1911번 - 흙길 보수하기 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2초 128MB 4472 1637 1268 37.593% 문제 어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N (1 > N >> L; priority_queue PQ; for (int i = 0; i > s >> e; e--; // [s, e] PQ.push({s, e}); } int c = 0, ans = 0; while (!PQ.empty()) { auto[s, e] = PQ.top(); PQ.pop(); if (s

백준 5214번 - 환승 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2초 256MB 7552 1928 1316 26.320% 문제 아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까? 입력 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다. 출력 첫째 줄에 1번역에서 N번역으로 가는데 방문하는 역의 개수의 ..

백준 3109번 - 빵집 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1초 256MB 15889 5491 3631 31.053% 문제 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다. 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다. 빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다. 원웅이는 가스관과 빵집을 연결하는 파이프를 설치하려고 한다. 빵집과 가스관 사이에는 건물이 있을 수도 있다. 건물이 있는 경우에는 파이프..

백준 1520번 - 내리막 길 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2초 128MB 56499 15516 11041 27.909% 문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다. 지도가 주어질 때 이..