[BOJ 22871] 징검다리 건너기 (large)

📃 문제

https://www.acmicpc.net/problem/22871

22871번: 징검다리 건너기 (large)

---

💻 코드

#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문 이용해서 반복