Notice
Recent Posts
Recent Comments
Link
์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
Tags
- Spring
- ์คํ๋ง๋ถํธ
- ssafy job fair
- SSAFY
- Security
- ์คํ๋ง
- ์๊ณ ๋ฆฌ์ฆ
- react
- ssafy 12๊ธฐ
- MySQL
- ๋ถ์ธ๊ฒฝ์บ ํผ์ค
- ๋ฐฑ์ค
- ์ธํผ์
- ํ์๊ฐ์
- viroreact
- IntelliJ
- viro-community
- SSAFYcial
- ์ธํผ
- ๋ฆฌ์กํธ
- arduino uno wifi rev2
- boj
- viro
- connetion refused
- SSAFY 11๊ธฐ
- Lombok
- React Native CLI
- ์ธํผ12๊ธฐ
- maven
- springboot
Archives
- Today
- Total
log
[BOJ 22871] ์ง๊ฒ๋ค๋ฆฌ ๊ฑด๋๊ธฐ (large) ๋ณธ๋ฌธ
๐ ๋ฌธ์
https://www.acmicpc.net/problem/22871
๐ป ์ฝ๋
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
int N;
long long bridge[1000001];
long long dp[1000001] = { 0 };
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N;
for (int i = 0; i < N; i++) cin >> bridge[i];
for (int i = 1; i < N; i++) dp[i] = 987654321; // ์ต์๊ฐ์ ๊ตฌํด์ผ ํ๊ธฐ ๋๋ฌธ์ ์ต๋ํ ํฐ ์๋ก ์ด๊ธฐํ
for (int i = 1; i < N; i++) {
for (int j = 0; j < i; j++) {
dp[i] = min(dp[i], max(dp[j], (i - j) * (1 + abs(bridge[j] - bridge[i]))));
}
}
cout << dp[N - 1] << '\n';
}
๋ฉ๋ชจ๋ฆฌ ๋ฐ ์๊ฐ
๐ก ํ์ด
- ์ ๋ ฅ๋ฐ์ ๋ฐ์ดํฐ ์ ์ฅ
- ์ ํ์
- max(dp[j], (i - j) * (1 + abs(bridge[j] - bridge[i]))));
- dp[j] : j๊น์ง ์ด๋ํ๋๋ฐ ๋ฐ์ํ ํ
- (i - j) * (1 + abs(bridge[j] - bridge[i]))) : i๋ฒ์งธ ๋๋ก ์ด๋ํ ๋ ๋ฐ์ํ๋ ํ ๊ณ์ฐ
- max ํจ์ ์ฌ์ฉ ์ด์ : ๋ฌธ์ ์์ "๋์ ํ๋ฒ ๊ฑด๋๊ฐ ๋๋ง๋ค ์ธ ์ ์๋ ํ์ ์ต๋ K์ด๋ค." → ํ์ ์ํ์ ๊ตฌํ๊ธฐ
- min(dp[j], ~)
- min ํจ์ ์ฌ์ฉ ์ด์ : K์ ์ต์๊ฐ์ ๊ตฌํด์ผ ํ๋ค
- for๋ฌธ ์ด์ฉํด์ ๋ฐ๋ณต
'Algorithm > Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ 1863] ์ค์นด์ด๋ผ์ธ ์ฌ์ด๊ฑฐ (1) | 2024.04.07 |
---|---|
[BOJ 2110] ๊ณต์ ๊ธฐ ์ค์น (0) | 2024.03.14 |