전체 글 (493) 썸네일형 리스트형 [Gold V] 개똥벌레 - 3010 [문제 위치]https://www.acmicpc.net/problem/3020[문제 풀이]이 문제는 고정 합 문제이다.문제의 핵심 몇 가지를 정리하자면 이 문제의 개똥벌래는 오직 직진만을 할 수 있다.장애물이 있으면 부수고 나아갈 정도로 직진만한다.그리고 장애물은 석순과 석주 두 가지로 나누어져 있으며 종류에 따라 바닥에서 시작하는지 천장에서 시작하는지가 나뉜다.이 문제는 최소한의 장애물을 부수고 나가는 경우 해당 종유석의 숫자를 구하는 문제다.따라서 개똥벌레가 출발할 때 선택한 높이를 가로막는 벽들의 누적합을 구하면 된다.이를 위해 IMOS 방법을 이용하였다.석순의 경우 0(바닥)에서부터 h까지를 IMOS로 표시하였고 종유석의 경우 천장에서부터로 하였다.아래는 이를 구현한 코드이다.#include us.. [Silver V] Generations of Tribbles - 9507 [문제 위치]https://www.acmicpc.net/problem/9507[문제 풀이]이 문제는 피보나치 수열의 약한 변형 문제이다.점화식의 종류가 피보나치와 다른데 바로 이전 수를 두 번 곱해서 5번째 수를 한 번 빼주는 것과 그 결과가 같기 때문에 그 부분은 단순화 해주었다.나머지는 전형적인 바텀업 문제로 점화식을 반복문으로 처리해주면 된다.#include #include using namespace std;#define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr);int main() { FASTIO; int t; cin >> t; for (int k = 0; k > n; vector DP = { 1, 1,.. [Silver V] Entering the Time - 20746 [문제 위치]https://www.acmicpc.net/problem/20746[문제 풀이]이 문제는 유효한 시각 24×60=1440개를 정점으로 보고, 네 자리 중 한 자리를 ±1(0↔9 순환) 바꿔서도 시각이 여전히 유효하면 간선으로 연결한 뒤, 시작 시각에서 목표 시각까지의 최단 경로를 구하는 BFS 문제이다. 각 조작은 한 자리만 1만큼 변화시키고 중간 상태도 항상 유효해야 한다.BFS로 최단거리와 parent를 저장한 뒤, 목표에서 시작으로 역추적해 경로(시각들의 나열)를 출력하면 된다#include #include #include #include #include using namespace std;#define FASTIO ios::sync_with_stdio(false); cin.tie(nu.. [Silver IV] Leapcow - 27041 [문제 위치]https://www.acmicpc.net/problem/27041[문제 풀이]이 문제는 0에서 e까지 이동할 때 한 번에 최대 l만큼 앞으로 점프할 수 있고, b개의 위치는 착지할 수 없을 때(금지 위치) 최소 점프 횟수를 구하는 그리디 문제이다.풀이 핵심은 현재 위치 i에서 갈 수 있는 가장 먼 곳 r = min(i+l, e)부터 왼쪽으로 내려오며 착지 가능한 지점을 찾고, 그중 가장 오른쪽(가장 멀리)으로 착지하는 것이 항상 최적이라는 점이다. 매번 가능한 한 멀리 가면 남은 거리가 줄어들기 때문에 점프 횟수가 늘 이유가 없다. 금지 위치가 많을 때 매번 선형으로 뒤로 훑는 대신, DSU(분리 집합)로 x 이하에서 가장 가까운 착지 가능 위치(전임자)를 빠르게 찾도록 구현했다.#incl.. [Silver IV] It Is Cold - 9354 [문제 위치]https://www.acmicpc.net/problem/9354[문제 풀이]이 문제는 오른쪽에서 오는 바람이 팀(왼쪽)까지 실제로 도달하는 “순수한 T 방향(팀 쪽) 바람의 세기”를 구하는 시뮬레이션(그리디 누적) 문제이다. 두 선풍기가 마주보면 세기가 상쇄되고, 같은 방향이면 합쳐진다. 핵심은 A 방향(팀 반대) 바람은 팀 쪽으로 진행하지 못하고, 오로지 오른쪽에서 오는 T 바람을 깎는 역할만 한다는 점이다. 그래서 맨 오른쪽 선풍기부터 왼쪽으로 보며, 현재 위치를 통과해 팀 쪽으로 진행 중인 바람의 세기 cur만 유지한다. 현재 선풍기가 T면 cur += S 현재 선풍기가 A면 cur -= S (T 바람을 상쇄) cur 이 과정을 끝내면 cur이 답이다.아래는 이를 구현한 코드이다.#i.. [Silver IV] Szyfr - 17968 [문제 위치]https://www.acmicpc.net/problem/8546[문제 풀이]이 문제는 DP를 활용하는 문제이다. 피보나치 수열의 일반적 구현이다.다만, 시간 초과를 막기 위해 피사노 주기를 통한 상수 계산을 해주어야 한다는 점이 구분 점이다.#include #include #include #include using namespace std;#define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr);int main() { FASTIO long long n, m; cin >> n >> m; int last[60]; last[0] = 0; last[1] = 1; for (int i = 2; i (len, 60.. [Silver IV] Fire on Field - 17968 [문제 위치]https://www.acmicpc.net/problem/8582[문제 풀이]이 문제는 서쪽(자기 포함)에서의 최댓값과 동쪽(자기 포함)에서의 최댓값을 각 위치마다 출력하는, 전형적인 prefix maximum / suffix maximum 문제이다. 입력으로 높이 w1..wn이 주어지면 i번째에 대해 ai = max(w1..wi), bi = max(wi..wn)을 구해 n줄로 출력하면 된다. n이 최대 1,000,000이므로 O(n^2)은 불가하고, 한 번 왼쪽→오른쪽, 한 번 오른쪽→왼쪽으로 훑는 O(n) 풀이가 정답이다.#include #include using namespace std;#define FASTIO ios::sync_with_stdio(false); cin.tie(null.. [Silver V] 점화식 - 13699 [문제 위치]https://www.acmicpc.net/problem/13699[문제 풀이]이 문제는 주어진 점화식을 DP로 구현하면 되는 간단한 문제이다. t(0) = 1t(n) = Σ (i=0..n-1) t(i) * t(n-1-i)아래는 이를 구현한 코드이다. #include #include using namespace std;#define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr);int main() { FASTIO int n; cin >> n; vector t(n + 1, 0); t[0] = 1; for (int k = 1; k 이전 1 2 3 4 ··· 62 다음