ํ๊ต์์ ๊ทธ๋ํฝ์ค ์์ ์ ๋ค์ ๋์ค์ด๋ ์์ ์๊ฐ์ ๋ค์ ๋ด์ฉ์ ๋ฐํ์ผ๋ก ์ค๋งํธํฐ ๊ฒ์์ ๋ง๋ค์๋ค. ๊ฒ์์๋ ์ด N๊ฐ์ ๋ ๋ฒจ์ด ์๊ณ , ๊ฐ ๋ ๋ฒจ์ ํด๋ฆฌ์ดํ ๋ ๋ง๋ค ์ ์๊ฐ ์ฃผ์ด์ง๋ค. ํ๋ ์ด์ด์ ์ ์๋ ๋ ๋ฒจ์ ํด๋ฆฌ์ดํ๋ฉด์ ์ป์ ์ ์์ ํฉ์ผ๋ก, ์ด ์ ์๋ฅผ ๋ฐํ์ผ๋ก ์จ๋ผ์ธ ์์๋ฅผ ๋งค๊ธด๋ค. ๋์ค์ด๋ ๋ ๋ฒจ์ ๋์ด๋ ์์ผ๋ก ๋ฐฐ์นํ๋ค. ํ์ง๋ง, ์ค์๋ก ์ฌ์ด ๋ ๋ฒจ์ด ์ด๋ ค์ด ๋ ๋ฒจ๋ณด๋ค ์ ์๋ฅผ ๋ง์ด ๋ฐ๋ ๊ฒฝ์ฐ๋ฅผ ๋ง๋ค์๋ค.
์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ๋์ค์ด๋ ํน์ ๋ ๋ฒจ์ ์ ์๋ฅผ ๊ฐ์์ํค๋ ค๊ณ ํ๋ค. ์ด๋ ๊ฒํด์ ๊ฐ ๋ ๋ฒจ์ ํด๋ฆฌ์ดํ ๋ ์ฃผ๋ ์ ์๊ฐ ์ฆ๊ฐํ๊ฒ ๋ง๋ค๋ ค๊ณ ํ๋ค.
๊ฐ ๋ ๋ฒจ์ ํด๋ฆฌ์ดํ ๋ ์ป๋ ์ ์๊ฐ ์ฃผ์ด์ก์ ๋, ๋ช ๋ฒ ๊ฐ์์ํค๋ฉด ๋๋์ง ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ์๋ ํญ์ ์์์ด์ด์ผ ํ๊ณ , 1๋งํผ ๊ฐ์์ํค๋ ๊ฒ์ด 1๋ฒ์ด๋ค. ํญ์ ๋ต์ด ์กด์ฌํ๋ ๊ฒฝ์ฐ๋ง ์ฃผ์ด์ง๋ค. ์ ๋ต์ด ์ฌ๋ฌ ๊ฐ์ง์ธ ๊ฒฝ์ฐ์๋ ์ ์๋ฅผ ๋ด๋ฆฌ๋ ๊ฒ์ ์ต์ํ์ผ๋ก ํ๋ ๋ฐฉ๋ฒ์ ์ฐพ์์ผ ํ๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ๋ ๋ฒจ์ ์ N์ด ์ฃผ์ด์ง๋ค. (1 โค N โค 100) ๋ค์ N๊ฐ ์ค์๋ ๊ฐ ๋ ๋ฒจ์ ํด๋ฆฌ์ดํ๋ฉด ์ป๋ ์ ์๊ฐ ์ฒซ ๋ฒ์งธ ๋ ๋ฒจ๋ถํฐ ๋ง์ง๋ง ๋ ๋ฒจ๊น์ง ์์๋๋ก ์ฃผ์ด์ง๋ค. ์ ์๋ 20,000๋ณด๋ค ์์ ์์ ์ ์์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ์ ์๋ฅผ ๋ช ๋ฒ ๊ฐ์์ํค๋ฉด ๋๋์ง ์ถ๋ ฅํ๋ค.
๐ก ๋ค์์ ๋ถํฐ ๋ฐฐ์ด์ ํ์ํ๋ฉด์ ์์ ์์๊ฐ ๋ค์ ์์๋ณด๋ค -1๋๋๋ก ์์ ํจ
for(int i=n-1; i>=1; i--) {
if(arr[i-1] >= arr[i]) {
sum += arr[i-1]-arr[i]+1;
arr[i-1] = arr[i]-1;
}
}
import java.io.*;
public class BOJ_2847 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
for(int i=0; i<n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
int sum = 0;
for(int i=n-1; i>=1; i--) {
if(arr[i-1] >= arr[i]) {
sum += arr[i-1]-arr[i]+1;
arr[i-1] = arr[i]-1;
}
}
System.out.println(sum);
}
}
์ฑ๊ณตโจ