[이것이 코딩테스트다] 20일차 - DP 문제풀이 | 금광, 정수삼각형, 퇴사, 병사 배치하기

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다.

Chapter 8 다이나믹 프로그래밍

오늘 풀이한 문제 - 다이나믹 프로그래밍 예제

[이코테 375p] 금광

문제

n × m 크기의 금광이 있다. 금광은 1 × 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있다

채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작한다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있다.
이후에 m - 1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다.
결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하라

 

접근 방법

드디어 혼자 점화식을 세워보았다

현재 위치에 있을때, 얻을수 있는 최대 금의 크기는 

max(현재 위치+왼쪽 위, 현재위치+바로 왼쪽, 현재 위치+왼쪽 아래)이다

하지만 현재 위치가 어디냐에 따라 왼쪽 위, 아래는 접근할 수 없기때문에 조건문을 사용하여 좌표를 지정해준다

 

소스 코드

n,m = map(int, input().split())
data = list(map(int, input().split()))

gold_map = []
cnt = 0
for _ in range(n):
    gold_map.append(data[cnt:cnt+m])
    cnt += m
    
for i in range(1, m):
    for j in range(n):
    	## 왼쪽 위 접근 불가
        if j == 0:
            up = 0
        else: 
            up = gold_map[j-1][i-1]
            
        ## 왼쪽 아래 접근 불가
        if j == n-1:
            down = 0
        else:
            down = gold_map[j+1][i-1]
            
        ## 바로 왼쪽은 항상 가능
        side = gold_map[j][i-1]
        gold_map[j][i] = max(gold_map[j][i]+up, gold_map[j][i]+down, gold_map[j][i]+side)
        
print(max(gold_map[-1]))

 

[백준 1932] 정수 삼각형

1932번: 정수 삼각형

문제

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

 

접근 방법

금광 문제와 유사하게 풀이할 수 있다!!

이 문제의 점화식은 max(현재 삼각형의 값 + 오른 대각선 값, 현재 삼각형의 값 + 왼쪽 대각선의 값) 이다

한 쪽 대각선에 접근할 수 없을때는 그냥 다른쪽 대각선의 값을 더하면 된다

 

소스 코드

n = int(input())
dp = []
for _ in range(n):
    dp.append(list(map(int, input().split())))
    
for i in range(1,n):
    for j in range(i+1):
    	## 왼쪽 대각선 접근 불가
        if j == 0:
            dp[i][j] += dp[i-1][j]
        ## 오른 대각선 접근 불가
        elif j == i:
            dp[i][j] += dp[i-1][j-1]
        ## 두 대각선 모두 가능
        else:
            dp[i][j] = dp[i][j] + max(dp[i-1][j], dp[i-1][j-1])
            
print (max(dp[-1]))

 

[백준 14501] 퇴사

14501번: 퇴사

문제

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

 

	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200

 

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

 

접근 방법

점화식 세우기 실패,, 다른사람 점화식을 살짝 이해해봤다

일단 맨 뒤에서부터 접근한다 (dp 리스트 값이 그래서 table 길이보다 하나 더 길어야 함)

남은 일수보다 상담에 필요한 일수가 더 길면 다음날의 수익 그대로 사용 (오늘 일 안함)

그게 아닐경우

max(오늘 일을 안하는 경우 -> pay는 미리 계산한 다음날 값과 변동 x, 일을 하는 경우 -> 일을 하는 시간만큼 뒤로 간다음 그곳의 pay와 더함)

 

소스 코드

n = int(input())
table = []
for _ in range(n):
    table.append(list(map(int, input().split())))
dp = [0]*(n+1)
for day in range(n-1, -1,-1):
    t, p = table[day]
    if day + t > n:
        dp[day] = dp[day+1]
    else:
        dp[day] = max(dp[day+1], p+dp[day+t])
print (dp[0])

 

 

[이코테 375p] 금광

문제

18353번: 병사 배치하기

N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다.

또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다.

예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자.

이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는 병사의 수가 최대가 되도록 하는 방법이다.

병사에 대한 정보가 주어졌을 때, 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력하는 프로그램을 작성하시오.

 

 

접근 방법

이는 최장 증가 부분 수열 (LIS)를 이용하면 쉽게 풀이할 수 있다고 한다

그걸 몰라서 처음에는 이게 왜 dp지?? 하다가 리스트 앞 뒤 값을 비교해가며 크면 추가하는 식으로 풀었다 ,, (예시는 통과인데 백준에서는 당연히 틀렸음)

 

LIS는 일단 1로 dp를 채운다 (가장 짧은 수열의 길이는 1이기 때문)

input 수열을 돌면서 지금보다 더 큰수가 나오면 

0~지금 바로 전까지의 dp+1과 지금 dp값 중 큰값을 저장한다 

-> max(dp[now], dp[front]+1)

 

소스 코드

n = int(input())
army = list(map(int, input().split()))
## 최장 증가 부분 수열 (LIS) 활용
army.reverse()

dp = [1]*n

for now in range(1,n):
    for front in range(0,now):
        if army[front] < army[now]:
            dp[now] = max(dp[now], dp[front]+1)

print (n - max(dp))

👇 틀린 풀이 ^^,,

## 틀린 풀이도 살포시,,^^
n = int(input())
army = list(map(int, input().split()))

dp = []
for i in range(n-1):
    if army[i] > army[i+1]:
        dp.append(max(army[i], army[i+1]))
    if i == (n-2):
        if dp[-1] > army[-1]:
            dp.append(army[-1])
            
print (n- len(dp))