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

 

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

 

징검다리 건너기 (large)

 

 

문제

N개의 돌이 일렬로 나열 되어 있다. N개의 돌에는 왼쪽부터 차례대로 수 A_1 A_2 A_3 ... A_i .. A_N로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다.

1. 항상 오른쪽으로만 이동할 수 있다.
2. i번째 돌에서 j(i<j)번째 돌로 이동할 때 (j - i) × (1 + |A_i - A_j|) 만큼 힘을 쓴다.
3. 돌을 한번 건너갈 때마다 쓸 수 있는 힘은 최대 K이다.

가장 왼쪽 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너갈 수 있는 모든 경우 중 K의 최솟값을 구해보자.

입력

첫 번째 줄에 돌의 개수 N이 공백으로 구분되어 주어진다.

두 번째 줄에는 N개의 돌의 수 A_i가 공백으로 구분되어 주어진다.

출력

가장 왼쪽 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너갈 수 있는 모든 경우 중 가능한 K의 최솟값을 출력한다.

제한

•  2≤N≤5,000
•  1≤A_i≤1,000,000
• A_i는 정수

예제 입력 1 

5
1 4 1 3 1

예제 출력 1 

2

예제 입력 2 

5
1 5 2 1 6

예제 출력 2 

6

 

---

풀이

 

처음 이 문제를 이해하는데 어려웠다. 도대체 구하라는 값이 뭘까...?

문제를 제대로 이해하지 못하니 예제에서 해당 출력이 어떻게 나오는 건지 감이 안잡혔다.

그래서 여기저기서 풀이를 찾아봤는데 솔직히 풀이를 봐도 제대로 이해가 안되서 손으로 하나씩 적으면서 이해를 했다.

 

해당 문제에서 구하라는 것은 왼쪽에서 오른쪽 돌까지 이동할 때 들어가는 최대 힘 K를 모든 경우에서 K의 최솟값을 말한다.

즉, 힘의 상한선을 정하고 그 이하의 힘만을 사용하여 마지막 다리까지 도달하는데 그때 힘의 최솟값을 구하라는 것이다.

 

이렇게 말로 설명해도 무슨 소리인지 이해하기 힘들었다.

 

 

예제로 살펴보자.

 

입력값이 예제 1인 경우, 다음과 같이 나타낼 수 있다.

왼쪽에서 오른쪽까지 모두 탐색을 하면서 경로에 필요한 최대 힘의 최솟값을 구하면 된다.

 

 

직접 손으로 만들어보니 이해하기 수월하였다.

 

 

---

설계

 

이제 구해야 할 답은 왼쪽에서 오른쪽까지 모두 탐색을 하면서 경로에 필요한 최대 힘의 최솟값이다.

최대 힘의 최솟값이라,,, 문제를 왜 이렇게 애매하게 설명해서 이해하는 데 어려움을 준 것일까,,, 

 

1️⃣ 어떻게 탐색

 

일단 왼쪽에서 오른쪽으로 어떻게 탐색할 것인지에 대해 생각해보자.

나는 재귀함수로 첫 번째 돌부터 마지막 돌까지 탐색하였고, dp[] 배열을 사용하였다.

 

2️⃣ 최대 힘의 최솟값

 

• max(앞에 저장된 힘, 새롭게 구한 힘)의 최솟값

 

---

구현

 

1️⃣ 어떻게 탐색

 

 

• 기저사례를 두고 반복문을 사용하여 N까지 탐색

 

func jump(_ i: Int) -> Int{
    
    if i==N-1{
        return 0
    }
   
    for j in stride(from: i+1, to: N, by: 1){
		...
    }
    return dp[i]
}

 

 

 

2️⃣ 최대 힘의 최솟값

 

• dp[]배열을 -1로 초기화하고, -1 값이 아니라면 저장된 값을 return
• -1 값이라면 dp를 Int.max 값으로 설정하여 반복문에서 힘 비교
• 모든 경우의 수의 최댓값의 최솟값 구하기
• 최종적으로 jump()의 리턴값이 최솟값

 

func jump(_ i: Int) -> Int{
    
    if i==N-1{
        return 0
    }
    if (dp[i] != -1) {
        return dp[i];
    }
    
    dp[i] = Int.max
    
    for j in stride(from: i+1, to: N, by: 1){
        let maxPower = max(jump(j),(j-i)*(1+abs(arr[i]-arr[j])))
        dp[i] = min(dp[i], maxPower)

    }
    return dp[i]
}

 

 

 

---

전체코드

 

let N = Int(readLine()!)!

var arr = [Int](repeating: 0, count: N)
var dp = [Int](repeating: -1, count: N)

let input = readLine()!.split(separator: " ").map{Int(String($0))!}

for i in 0..<input.count {
    arr[i] = input[i]
}

func jump(_ i: Int) -> Int{
    
    if i==N-1{
        return 0
    }
    if (dp[i] != -1) {
        return dp[i];
    }
    
    dp[i] = Int.max
    
    for j in stride(from: i+1, to: N, by: 1){
        let maxPower = max(jump(j),(j-i)*(1+abs(arr[i]-arr[j])))
 
        dp[i] = min(dp[i], maxPower)

    }
    return dp[i]
}

print(jump(0))