-
[99클럽/코딩테스트 챌린지/C++]게임 레벨 점수를 최소한으로 감소시켜 순서대로 증가시키기2024년 11월 12일
- 유니얼
-
작성자
-
2024.11.12.:47
728x90문제 링크 :
https://www.acmicpc.net/problem/2847
문제 설명
동준이가 만든 게임에는 여러 레벨이 있고, 각 레벨을 클리어할 때 점수를 얻는다. 이 점수는 레벨이 높아질수록 커져야 하지만, 현재는 쉬운 레벨의 점수가 어려운 레벨보다 높은 경우가 존재한다. 이를 해결하기 위해 각 레벨의 점수를 감소시켜야 하며, 이때 최소한의 감소 횟수로 점수를 조정하는 것이 목표다.
접근법
이 문제는 그리디 알고리즘을 사용하여 해결할 수 있다. 가장 높은 레벨부터 점검하며, 현재 레벨 점수가 이전 레벨보다 낮거나 같을 경우 이전 레벨의 점수를 현재 레벨보다 1 낮게 만든다. 이 과정을 반복하면서 각 레벨의 점수를 점진적으로 감소시키며, 필요할 때마다 감소 횟수를 누적하여 최종 답을 도출한다.
#include <iostream> #include <vector> #include <set> #include <string> #include <math.h> #include <map> #include <queue> using namespace std; int main() { int N = 0; std::cin >> N; vector<int> levels(N); for (size_t i = 0; i < N; i++) { std::cin >> levels[i]; } int count = 0; for (size_t i = levels.size() - 1; i > 0; i--) { while (levels[i] <= levels[i - 1]) { levels[i - 1]--; count++; } } std::cout << count << '\n'; return 0; }
코드 설명
- 데이터 입력: 각 레벨의 점수를 벡터에 저장한다.
- 감소 작업 수행: 가장 높은 레벨부터 시작하여, 점수를 확인하면서 이전 레벨의 점수가 현재 레벨 점수보다 크거나 같을 경우 점수를 감소시킨다.
- 결과 출력: 총 감소 횟수를 출력한다.
배운 점
이 문제를 통해 그리디 알고리즘을 활용하여 역방향으로 접근하는 방식이 유효한 경우를 배웠다. 이와 같이, 높은 레벨부터 감소를 진행하는 방식이 문제의 최적 해법임을 깨달았다.
결론
이 문제는 그리디 알고리즘으로 각 레벨 점수가 증가하도록 조정하는 것이 핵심이었다. 필요할 때마다 점수를 최소로 감소시키며 문제를 해결할 수 있었고, 앞으로도 유사한 문제에서 그리디 접근법을 효과적으로 적용할 수 있을 것이다.
반응형다음글이전글이전 글이 없습니다.댓글
스킨 업데이트 안내
현재 이용하고 계신 스킨의 버전보다 더 높은 최신 버전이 감지 되었습니다. 최신버전 스킨 파일을 다운로드
받을 수 있는 페이지로 이동하시겠습니까?
("아니오" 를 선택할 시 30일 동안 최신 버전이
감지되어도 모달 창이 표시되지 않습니다.)