알고리즘 문제풀이

백준 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

링크 디펜스 게임 문제의 조건을 확인해보면 문제가 원하는 답이 무엇인지는 추측할 수 있으나 접근하는 방법을 떠올리기 쉽지 않다. 문제에서 주어진 조건을 정리해보면 아래와 같다 준호는 초기 $n$ 명의 병사를 가진다. 매 라운드마다 enemy[i] 마리의 적이 등장한다 무적권은 $k$ 번 사용할 수 있다 행위 현재 남은 병사보다 적이 더 많을 경우 게임은 종료 현재 남은 병사보다 적이 더 적을 경우 게임을 진행 무적권을 사용할 경우 병사의 수가 줄지 않는다 무적권을 사용하지 않을 경우 병사의 수가 줄어든다. Target := 무적권을 최대 $k$ 번 사용하여 준호가 진행할 수 있는 최대 라운드는? 이제 Constraint도 고려해보자. 1 $\leq$ n $\leq$ $10^9$ 1 $\leq$ k $\l..

백준 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 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다. 원웅이는 가스관과 빵집을 연결하는 파이프를 설치하려고 한다. 빵집과 가스관 사이에는 건물이 있을 수도 있다. 건물이 있는 경우에는 파이프..