[BOJ] 백준_2847번_게임을 만든 동준이_C/C++백준 알고리즘2022. 1. 27. 10:00
목차
문제 출처
https://www.acmicpc.net/problem/2847
문제 설명
코드
//[BOJ] 2847번 게임을 만든 동준이
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int N, result=0;
cin >> N;
int* arr = new int[N];
for (int i = 0; i < N; i++)
{
cin >> arr[i];
}
reverse(arr, arr + N);
for (int i = 1; i < N; i++)
{
if (arr[i] >= arr[i-1])
{
int a = arr[i] - arr[i-1] + 1;
arr[i] -= a;
result += a;
}
}
cout << result;
return 0;
}
풀이 과정
점수들을 arr 배열에 입력받은 뒤 점수를 감소시키는 방법만 존재하므로 맨 마지막 점수부터 탐색하기 위해 reverse 함수로 배열을 뒤집었다. 뒤집은 배열의 첫 인덱스는 마지막 점수이고 다음 점수가 될 수록 1이라도 작아져야만 한다. 때문에 인덱스 1 부터 마지막 점수까지 반복시키며 현재 점수가 이전 점수보다 크거나 같은지 찾는다. 크거나 같다면 하나라도 작게 만들어야 하므로 현재 점수와 이전 점수의 차에서 1을 더해준 만큼을 현재 점수에서 빼준다. 예를 들어 현재 점수arr[i]가 5이고 이전 점수arr[i-1]가 4이면 뒤집은 배열이므로 다음 라운드 배점은 4, 이전 라운드 배점은 5라는 뜻이고 다음 라운드가 이전 라운드보다 배점이 1 작기 때문에 라운드가 지날 수록 점수가 높아야 한다는 조건에 부합하지 않는다. 그렇다면 이전 라운드 점수 배점을 다음 라운드 배점 보다 1 작게 감소시키는 것이 최소한의 횟수를 소모하는 방법이다. 그렇기 때문에 이전 라운드 점수, 즉 현재 점수 arr[i]에서 그 둘의 차+1한 값을 빼준다. a 변수를 반복될 때마다 선언해서 해당 값을 담았고 그 만큼의 횟수를 소모한 것이므로 따로 선언해 둔 result 변수에 계속 더해준다. 총 횟수는 result 값이 된다.
728x90
반응형
LIST
'백준 알고리즘' 카테고리의 다른 글
[BOJ] 백준_16953번_A → B_C/C++ (0) | 2022.02.02 |
---|---|
[BOJ] 백준_1543번_문서 검색_C/C++ (0) | 2022.01.31 |
[BOJ] 백준_1260번_DFS와 BFS_C/C++ (0) | 2022.01.26 |
[BOJ] 백준_1449번_수리공 항승_C/C++ (0) | 2022.01.25 |
[BOJ] 백준_5585번_거스름돈_C/C++ (0) | 2022.01.23 |
@kdj :: Childev'note
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!