Algorithm TIL (240911)

> [백준] 예산

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

 

🔥다시 풀기🔥

 

 

문제 풀이 과정

• 우선 각 지방의 예산 금액들과 총 예산이 주어진다. 주어지는 총액을 만족하는 각 지방의 예산 상한액을 출력해야 한다. 
• 각 지방의 예산 상한액은 지방이 가진 예산을 초과할 수 없으며 만일 예산 상한액을 넘으면, 해당 지방의 예산까지만 요청할 수 있다.

 

• 우선 이 문제를 처음 봤을 때, 총예산까지 1을 더해주면서 찾으면 되지 않을까? 생각했는데, M의 범위가 10억이하이다. 그렇기 때문에 시간초과가 날 것이라고 예상할 수 있다.
• 그래서 힌트를 보니 이분탐색 방법이 있어서 이분탐색을 사용했다.
• 이분 탐색은 찾고자 하는 범위의 절반씩 줄여가며 탐색하는 방법이다. 범위를 지방 예산의 max 값까지로 설정하고 중간값을 구해 지방의 총 예산을 구했을 때, 주어지는 국가 예산 총액이 될때까지 반복한다.

문제 풀이

python

# 주어지는 지방 예산요청을 모두 합했을 때, maxNum 미만인 만큼 전해줄 수 있다. maxNum 이상일 수 없다.

n = int(input())
province = list(map(int, input().split()))
maxNum = int(input()) # 지방 총예산 최저값

# 지방의 예산요청을 모두 만족하는 예산 금액을 출력한다. (정수)
ans = 0
start, end = 1, max(province)
while start <= end :
    mid = (start + end) // 2
    total = 0 # 예산 합
    
    for pro in province :
        if pro > mid :
            total += mid
        else :
            total += pro
    
    if total <= maxNum : # 지방 총예산 최저값보다 적은 경우, start를 늘려 계산
        ans = mid
        start = mid + 1
    else : # 지방 총예산 최저값보다 큰 경우, end를 줄여 계산
        end = mid - 1
    
print(ans)

 

 

---

> [백준] 징검다리 건너기 (large)

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

 

🔥다시 풀기🔥

 

 

문제 풀이 과정

• 문제에서 구하는 출력 값이 애매하다고 생각했다. 처음에는 i번째 돌에서 j번째돌로 이동한다는 것이 1씩 이동할 수 있다는 건가?했는데.. 구간이 얼마드 왼쪽에서 오른쪽으로 이동할 수 있다는 의미라고 봐야하는 것이다.
• 그리고 문제에서 원하는 결과는 오른쪽 돌에 갈 수 있는 가능한 최대 K 중의 최솟값이었다. 
• 1 4 1 3 1 을 예로 들어보자면 맨 오른쪽 돌인 1로 왼쪽 돌에서 이동할 수 있는 각 거리는 아래와 같다. 때문에 2번째 위치한 돌인 1이 가장 적은 힘으로 목표지점에 이동할 수 있다.

• 그렇다면 맨 오른쪽 돌이 2번째 돌인 1일 때, 는 왼쪽 어디서 오는 힘이 가장 적을까? 0번째 돌인 1에서 오는 힘이 가장 적다.

• 이 부분을 이용해 d[i] 는 i번째까지 이동했을 때의 k(최소)라고 했을 때,  d[i]의 k값은 아래와 같다.
• 0부터 j까지의 힘과 j부터 i까지의 힘을 비교했을 때, 큰 값을 power라고 하고 이 power가 가장 적은 값을 d[i]로 한다.
  • d[i] = min(d[i], max( (i-j) * ( 1 + |stone[i] - stone[j]| ) , d[j] ))

 

문제 풀이

python

# ---------------------------------------------------
# 징검다리 건너기 (large)

# 우선 문제의 요구사항이 조금 애매함. 
# 가장 왼쪽에서 가장 오른쪽 돌로 이동했을 때 걸리는 최대 힘 K의 최솟값을 구하는 문제이다.
# 다이나믹 프로그래밍 사용

n = int(input())
stones = list(map(int, input().split()))
d = [1e9 for _ in range(n)] # d[i] 는 j부터 i까지 사용되는 최소 힘

d[0] = 0 # i=j가 같을 때 초기화
for i in range(1, n) :
    min_val = int(1e9)
    for j in range(0, i) :
        # 최소한의 k를 구하기 위해 왼쪽에 있는 돌과의 연산을 통해 j부터 i까지의 힘을 구한다.
        power = (i-j) * (1 + abs(stones[i]-stones[j]))
        # j부터 i까지의 힘과 처음돌 0부터 j까지의 돌 (i-1)까지의 힘을 비교해 큰 값을 power로 설정한다.
        power = max(power, d[j])
        # 구해진 power와 d[i] 중 최솟값을 반환
        if min_val >= power :
            min_val = power
    d[i] = min_val

print(d[n-1])

 

 

오늘의 회고 및 느낀점

알고 있는 개념이라고 생각했던 것들도 다시한번 풀어보자. 이분탐색과 DP 활용한 다양한 문제를 풀어 아이디어를 얻자..